看了书才做的和uva1626可以一起看（添加最少的括号使括号配对）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=105;
char str[maxn];
char s[4]="end";
int d[maxn][maxn],len;bool match(char a,char b)
{if((a=='('&&b==')')||(a=='['&&b==']'))return true;return false;
}void dp()
{/*for(int i=0;i<len;i++)for(int j=0;j<len;j++)d[i][j]=len;*//*for(int i=0;i<len;i++){//d[0][1]=2;//d[i][i+1]=2;d[i][i]=1;}*/for(int i=len-2;i>=0;i--)for(int j=i+1;j<len;j++){//d[i][j]=len;//cout<<1<< d[i][j]<<endl;if(match(str[i],str[j]))d[i][j]=d[i+1][j-1]+2;for(int k=i;k<j;k++)//if(match(str[i],str[k])&&match(str[k+1],str[j]))d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]);}
}int main()
{while(scanf("%s",str)!=EOF){if(!strcmp(str,s)) break;memset(d,0,sizeof(d));len=strlen(str);//cout<<1<<endl;dp();//for(int i=0;i<len;i++)//for(int j=0;j<len;j++)//cout<<"l:"<<len<<"d:"<<d[i][j]<<endl;printf("%d\n",d[0][len-1]);}return 0;
}