思路：区间dp,打印路径，详见http://www.cnblogs.com/widsom/p/8321670.html
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int N=;
int dp[N][N];
int pos[N][N];
string s;
void dfs(int l,int r){
if(l>r)return ;
if(l==r){
if(s[l]=='('||s[l]==')')cout<<"()";
else cout<<"[]";
}
else{
if(pos[l][r]==-){
cout<<s[l];
dfs(l+,r-);
cout<<s[r];
}
else{
dfs(l,pos[l][r]);
dfs(pos[l][r]+,r);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cin>>s;
for(int l=;l<=s.size();l++){
for(int i=;i+l-<s.size();i++){
int j=i+l-;
if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')dp[i][j]=dp[i+][j-]+,pos[i][j]=-;
for(int k=i;k<j;k++){
if(dp[i][k]+dp[k+][j]>=dp[i][j]){
dp[i][j]=dp[i][k]+dp[k+][j];
pos[i][j]=k;
}
}
}
}
dfs(,s.size()-);
return ;
}