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

Problem found.
This program crashes when the input string is empty.
----author