括号序列

#include<bits/stdc++.h>
using namespace std;
string s;
int f[105][105];
bool match(char a,char b){return ((a==‘(‘&&b==‘)‘)||(a==‘[‘&&b==‘]‘));}
void print(int l,int r){
    if(l>r)return;
    if(l==r){
        if(s[l]==‘(‘||s[l]==‘)‘)printf("()");
        else printf("[]");
        return;
    }
    if(match(s[l],s[r])&&f[l][r]==f[l+1][r-1])
     {printf("%c",s[l]),print(l+1,r-1),printf("%c",s[r]);return;}
    for(int k=l;k<r;k++)
        if(f[l][r]==f[l][k]+f[k+1][r])
            {print(l,k),print(k+1,r);return;}
}
int main(){
    int q;
    scanf("%d",&q);
    getchar();
    while(q--){
        memset(f,0,sizeof(f));
        getline(cin,s);
        getline(cin,s);
        int n=s.size();
        if(!n){puts("\n");continue;}
        for(int i=0;i<n;i++)f[i][i]=1,f[i+1][i]=0;
        for(int i=n-2;i>=0;i--)
         for(int j=i+1;j<n;j++){
            f[i][j]=n;
            if(match(s[i],s[j]))
              f[i][j]=min(f[i][j],f[i+1][j-1]);
            for(int k=i;k<j;k++)
             f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]); 
         }
        print(0,n-1);
        puts("");
        if(q)puts("");
    }
    return 0;
}