1 #include<iostream>  2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6  7 char s[105]; 8 int n; 9 int d[105][105];10 11 12 bool cmp(char a, char b)13 {14     return a == ‘(‘&& b == ‘)‘ || (a == ‘[‘&& b == ‘]‘);15 }16 17 void dp()18 {19 20     for (int i = 0; i < n; i++)21     {22         d[i + 1][i] = 0;    //初始化，对应于下面的d[i+1][j-1]23                             //也就是如果为()或[]，此时不需要添加括号24         d[i][i] = 1;        //这个对应于单个‘(‘、‘)‘、‘[‘、‘]‘的情况25     }26 27     //从短区间开始枚举28     for (int i = n - 2; i >= 0; i--)29     {30         for (int j = i + 1; j < n; j++)31         {32             d[i][j] = n;33             //如果为()or[]，则这最外面的不用管34             if (cmp(s[i], s[j]))     d[i][j] = min(d[i][j], d[i + 1][j - 1]);35             for (int k = i; k < j; k++)36                 d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j]);37         }38     }39 }40 41 42 void print(int i, int j)43 {44     if (i>j)    return;45     if (i == j)46     {47         if (s[i] == ‘(‘ || s[i] == ‘)‘)      cout << "()";48         else cout << "[]";49         return;50     }51     int ans = d[i][j];52     //如果和里面所要加的括号数一样，那么 i 和 j 是不需要加括号的53     if (cmp(s[i], s[j]) && ans == d[i + 1][j - 1])54     {55         cout << s[i];56         print(i + 1, j - 1);57         cout << s[j];58         return;59     }60 61     for (int k = i; k < j; k++)62     {63         if (ans == d[i][k] + d[k + 1][j])64         {65             print(i, k);66             print(k + 1, j);67             return;68         }69     }70 }71 72 int main()73 {74     //freopen("D:\\txt.txt", "r", stdin);75     int T;76     cin >> T;77     getchar();78     while (T--)79     {80         gets(s);81         gets(s);82         n = strlen(s);83         dp();84         print(0, n - 1);85         cout << endl;86         if (T) cout << endl;87     }88     return 0;89 }