当前区间f(i, j)分两种情况，一种是s[i]于s[j]符合要求，那么可以转移到f[i + 1][j - 1] 这样答案只会更小或者相等
第二种是直接分成两个部分， 即f[i][j] = f[i][k] + f[k + 1][j]，这个时候要取min
同时要注意第一种情况未必是最优的，要从一二两种情况里面取最优值
然后输出方面，按照答案反推，如果当前状态刚好等于其中一种情况，那么就递归下去，边界是
一个字符的时候输出两个字符。
另外学会用fgets，不用gets。fgets头文件cstdio， fgets(s, MAXN, stdin);
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
char s[MAXN];
int f[MAXN][MAXN], n;inline bool match(char a, char b)
{return (a == '(' && b == ')') || (a == '[' && b == ']');
}void work()
{REP(i, 0, n){f[i + 1][i] = 0;f[i][i] = 1;}for(int i = n - 1; i >= 0; i--)REP(j, i + 1, n){f[i][j] = n;if(match(s[i], s[j])) f[i][j] = f[i + 1][j - 1];REP(k, i, j)f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);}
}void print(int i, int j)
{if(i > j) return; if(i == j){if(s[i] == '(' || s[i] == ')') printf("()");else printf("[]");return;}int ans = f[i][j];if(match(s[i], s[j]) && ans == f[i + 1][j - 1]){putchar(s[i]); print(i + 1, j - 1); putchar(s[j]);return;}REP(k, i, j)if(ans == f[i][k] + f[k + 1][j]){print(i, k); print(k + 1, j);return;}
}void read(char* s)
{fgets(s, MAXN, stdin);
}int main()
{int T;scanf("%d", &T);read(s); read(s);while(T--){read(s);n = strlen(s) - 1;work();print(0, n -1);puts("");if(T) puts("");read(s);}return 0;
}