Solution
采用 区间 dp。
对于串 $s$，$f_{l,r}$ 表示使 $[l,r]$ 区间变为正规括号序列所需添加的最少括号数量。
初始化：
$l = r$ 时，区间 $[l,r]$ 中只有一个括号，添加一个与之匹配的括号即可，故 $f_{l,r} = 1$。
$l > r$ 时，不存在这种情况，$f_{l,r} = 0$。
$l < r$ 时，由于需取最小值，故 $f_{l,r} = +\infty$。
状态转移：
当 $s_l$ 与 $s_r$ 匹配时，最外层括号已经匹配，只需对里面进行操作，故 $f_{l,r} = f_{l+1,r-1}$。
枚举断点 $k$，$f_{l,r} = \min(f_{l,r},f_{l,k}+f_{k+1,r})$。
时间复杂度 $O(n^3)$。
输出：
根据 $f$ 数组，递归推出 dp 过程，具体实现见代码。
注意输入与输出格式！！！
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int inf = 1e9;
string s;
int f[maxn][maxn];
bool judge(int l,int r){
return (s[l]=='(' && s[r]==')') || (s[l]=='[' && s[r]==']');
}
void Out(int l,int r){
if(l > r) return ;
if(l == r){
if(s[l]=='(' || s[l]==')') cout<<"()";
else cout<<"[]";
return ;
}
if(f[l][r]==f[l+1][r-1] && judge(l,r)){
cout<<s[l];
Out(l+1,r-1);
cout<<s[r];
return ;
}
for(int k=l;k<r;k++){
if(f[l][r] == f[l][k]+f[k+1][r]){
Out(l,k);
Out(k+1,r);
return;
}
}
}
void solve(){
memset(f,0,sizeof(f));
getline(cin,s);
getline(cin,s);
int n = s.size();
s = 'a'+s;
for(int i=1;i<=n;i++){
f[i][i] = 1;
for(int j=i+1;j<=n;j++) f[i][j] = inf;
}
for(int i=2;i<=n;i++){
for(int l=1;l+i-1<=n;l++){
int r = l+i-1;
if(judge(l,r)) f[l][r] = f[l+1][r-1];
for(int k=l;k<r;k++){
f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]);
}
}
}
Out(1,n);
cout<<endl;
return ;
}
int main(){
int n;cin>>n;getchar();
while(n--){
solve();
if(n) cout<<endl;
}
return 0;
}