ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1183. Brackets Sequence

Help! WA at #13, Why?
Posted by liangyaxiong 23 May 2007 16:17
I use memoization to solve the promblem, but WA#13.
I have no idea about it(although I've been debugging for 2 days).
Can you help me?

Here's the code:
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
using namespace std;
ifstream fin("bracket.in");
ofstream fout("bracket.out");
string S;
inline bool isregular(int i,int j)
{
    if(j<i)    return true;
    else if(j==i)    return false;
    char stack[100];    int p=0;
    for(int k=i;k<=j;k++)
    {
        if(p==0)
        {
            if(S[k]=='('||S[k]=='[')    stack[p++]=S[k];
            else return false;
        }
        else{
            if(( stack[p-1]=='('&&S[k]==')' )||( stack[p-1]=='['&&S[k]==']' ))    p--;
            else if(S[k]==')'||S[k]==']')    return false;
            else    stack[p++]=S[k];
        }
    }
    return (p==0);
}
string s[100][100];
string memo(int i, int j)
{
    if(s[i][j]!="")    return s[i][j];
    if(isregular(i,j))
    {
        s[i][j].assign(S,i,j-i+1);
        return s[i][j];
    }
    if(i==j)
    {
        if(S[i]=='('||S[i]==')')    s[i][j]="()";
        else if(S[i]=='['||S[i]==']')    s[i][j]="[]";
        else assert(0);
        return s[i][j];
    }
    string ans,tmp,tmp2;
    unsigned size=UINT_MAX;
    if(( S[i]=='('&&S[j]==')' )||( S[i]=='['&&S[j]==']' ))
    {
        ans=S[i]+memo(i+1,j-1)+S[j];
        size=ans.size();
    }
    else if(( S[i]=='('&&S[j]!=')' )||( S[i]=='['&&S[j]!=']' ))
    {
        ans=S[i]+memo(i+1,j);
        if(S[i]=='(')    ans=ans+')';
        else if(S[i]=='[')    ans=ans+']';
        else assert(0);
        size=ans.size();
    }
    else if(( S[i]!='('&&S[j]==')' )||( S[i]!='['&&S[j]==']' ))
    {
        ans=memo(i,j-1)+S[j];
        if(S[j]==')')    ans='('+ans;
        else if(S[j]==']')    ans='['+ans;
        else assert(0);
        size=ans.size();
    }
    for(int k=i;k<j;k++)
        if(size>memo(i,k).size()+memo(k+1,j).size())
        {
            ans=memo(i,k)+memo(k+1,j);
            size=memo(i,k).size()+memo(k+1,j).size();
        }
    return (s[i][j]=ans);
}
int main()
{
    cin >> S;
    cout << memo(0,S.size()-1) << endl;
    return 0;
}

Edited by author 23.05.2007 16:19
Re: Help! WA at #13, Why?
Posted by Tom Tung 1 Jun 2007 12:34
Problem found.
This program crashes when the input string is empty.
----author