代码一：（超时）
#include<stdio.h>
#include<string.h>
int tag[110][110];//tag记录能否str[st]和str[end]中划分子问题，用opt[i][j]表示从str[st]到str[end]所需要插入的最小字符数
char str[128];
int opt[110][110];
void search(int st,int end)
{
	if(st>end)
		return ;
	else if(st==end) //如果剩下最后一个字符，为之配对
	{
		if(str[st]==')'||str[st]=='(')
			printf("()");
		else printf("[]");
		return ;
	}
	else if(tag[st][end]==-1)//如果str[st]和str[end]配对（tag==-1），打印str[st]和str[end],继续搜索str[st+1]和str[end-1]
	   {
		   printf("%c",str[st]);
	       search(st+1,end-1);
		   printf("%c",str[end]);
	   }
	 else if(tag[st][end]=-2)//如果str[st]和str[end]不配对（tag!=-1），搜索从tag分开的两个子问题
	   {
            if(str[st]=='(')
				printf("()");
			else printf("[]");
			search(st+1,end);
	   }
	 else if(tag[st][end]==-3) 
	   {
		   if(str[st]==')')
				printf("()");
			else printf("[]");
			search(st,end-1);
	   }
	 else
	 {search(st,tag[st][end]);
	 search(tag[st][end],end);
	 }
	
}
int main()
{
	int i,j,k,interval,tmp,len;
    gets(str);
		len=strlen(str);
		for(i=0;str[i]!='\0';i++)
		 if(str[i]==' ')
		    for(j=i;j<len;j++)
			  str[j]=str[j+1];
		len=strlen(str);
	   for(i=1;i<110;i++) //初始化
	   {
		   tag[i][i]=1;
		   tag[i][i-1]=0;
	   }
	   tag[0][0]=1;
	   for(interval=1;interval<len;interval++)  //从间隔1个字母到间隔len-1个字母分别计算tag
	      for(i=0;i+interval<len;i++)
		  {
			  j=i+interval;
              opt[i][j]=32767;
			  if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']')//如果str[i]和str[j]可以配对，问题转化为求str[i+1][j-1]的tag
			  {
				  if(opt[i+1][j-1]<opt[i][j])
				  {
					  tag[i][j]=-1;
					  opt[i][j]=opt[i+1][j-1];
				  }
			  }
              for(k=i;k<=j;k++)
			  {
				  if(opt[i][j]>opt[i][k]+opt[k][j])
				 {
					 opt[i][j]=opt[i][k]+opt[k+1][j];
				     tag[i][j]=k;
				 }
			  }
			  if(opt[i+1][j]+1<opt[i][j]&&(str[i]=='('||str[i]=='['))
			  {
				  opt[i][j]=opt[i+1][j]+1;
				  tag[i][j]=-2;
			  }
              if(opt[i][j-1]+1<opt[i][j]&&(str[j]==')'||str[j]==']'))
			  {
				  opt[i][j]=opt[i+1][j]+1;
				  tag[i][j]=-3;
			  }
		  }
		  search(0,len-1);
		  printf("\n");
	return 0;
}
代码二：（0Ms）
#include <iostream>
#include <algorithm>
#include <limits>

using namespace std;

int  result[101][101];
int  path[101][101]= {0};
char str[101];


void output( int i, int j )
{
    if ( i> j ) return;
    else if ( i== j ) 
    {
        if ( str[i]== '(' || str[i]== ')' )
            printf("()");
        else
            printf("[]");

        return;
    }
    else if ( path[i][j]== -1 )
    {
        printf("%c",str[i] );
        output( i+ 1, j- 1 );
        printf("%c",str[j] );
    }
    else if ( path[i][j]== -2 )
    {
        if ( str[i]== '(' )
        {
            printf("(");
            printf(")");
            output( i+ 1, j );
        }
        else 
        {
            printf("[");
            printf("]");
            output( i+ 1, j );
        }
    }
    else if ( path[i][j]== -3 )
    {
        if ( str[j]== ')' )
        {
            printf("(");
            output( i, j- 1 );
            printf(")");
        }
        else 
        {
            printf("[");
            output( i, j- 1 );
            printf("]");
        }
    }
    else 
    {
        output( i, path[i][j]    );
        output( path[i][j]+ 1, j );
    }
}

int main()
{
    while ( gets(str)!= NULL )
    {
        int len= strlen( str );
        int j= 0;
        for ( int i= 0; i< len; ++i )
        {
            if ( str[i]!= ' ' )
            {
                str[j]= str[i];
                j++;
            }
        }
        str[j]= '\0';
        len= strlen(str);

        for ( i= 1; i< len; ++i )
        {
            result[i][i-1]= 0;
            result[i][i]  = 1;
        }
        result[0][0]= 1;

        for (  i= 1; i< len; ++i )
        {
            for ( int j= 0; j< len- i; ++j )
            {
                int t= j+ i;
                result[j][t]= INT_MAX;

                if ( (str[j]== '(' && str[t]== ')')  || (str[j]== '[' && str[t]== ']' ) )
                {
                    if ( result[j+1][t-1]< result[j][t]  )
                    {
                        path[j][t]  = -1;
                        result[j][t]= result[j+1][t-1];
                    }
                }

                for ( int k= j; k<= t; ++k )
                        if ( result[j][t]> result[j][k]+ result[k+1][t] )
                        {
                            result[j][t]= result[j][k]+ result[k+1][t];
                            path[j][t]= k;
                        }
                
                if (  ( str[j]== '(' || str[j]== '[' ) && 
                      ( result[j+1][t]+ 1< result[j][t]  ) )
                {
                    result[j][t]= result[j+1][t]+ 1;
                    path[j][t]  = -2;
                }
                
                if (  ( str[t]== ')' || str[t]== ']' ) &&
                           ( result[j][t-1]+ 1< result[j][t]  ) )
                {
                    result[j][t]= result[j][t-1]+ 1;
                    path[j][t]= -3;
                }
            }
        }

        output( 0, len- 1 );
        printf("\n");
    }

    return 0;
}