http://www.cnblogs.com/20143605--pcx/p/4791122.html
Let us define a regular brackets sequence in the following way:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1a2...an is called a subsequence of the string b1b2...bm, if there exist such indices 1 ≤ i1 < i2 < ... < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Let us define a regular brackets sequence in the following way:
- Empty sequence is a regular sequence.
- If S is a regular sequence, then (S) and [S] are both regular sequences.
- If A and B are regular sequences, then AB is a regular sequence.
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1a2...an is called a subsequence of the string b1b2...bm, if there exist such indices 1 ≤ i1 < i2 < ... < in ≤ m, that aj=bij for all 1 ≤ j ≤ n.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
1 ([(]
Sample Output
()[()]
这是《入门经典》上的一道例题。如果仅让求最短序列是极简单的，定义dp(i,j)表示将区间 i~j 变为合法添加的最小字符数.
则 dp(i,j)=dp(i+1,j-1) （i与j能匹配时)， dp(i,j)=min(dp(i,k)+dp(k+1,j))。
但是，输出的时候就比较慢了。从左往右通过比较选择最优方案递归输出（看的书上代码）。
char p[105];int dp[105][105];const int INF=100000;bool match(int x,int y){ if(p[x]=='('&&p[y]==')') return true; if(p[x]=='['&&p[y]==']') return true; return false;}void DP(){ int len=strlen(p); for(int l=1;l<=len;++l){ for(int i=0;i+l-1<len;++i){ int r=i+l-1; if(l==1){ dp[i][r]=1; continue; } if(l==2){ if(match(i,r)) dp[i][r]=0; else dp[i][r]=2; continue; } dp[i][r]=INF; if(match(i,r)) dp[i][r]=dp[i+1][r-1]; for(int k=i;k<r;++k){ dp[i][r]=min(dp[i][r],dp[i][k]+dp[k+1][r]); } } }}void print(int i,int j){ if(i>j) return ; if(i==j){ if(p[i]=='('||p[i]==')') printf("()"); else printf("[]"); return ; } int ans=dp[i][j]; if(match(i,j)&&ans==dp[i+1][j-1]){ printf("%c",p[i]); print(i+1,j-1); printf("%c",p[j]); return ; } for(int k=i;k<j;++k){ if(ans==dp[i][k]+dp[k+1][j]){ print(i,k); print(k+1,j); return ; } }}int main(){ int T; scanf("%d",&T); getchar(); while(T--) { getchar(); gets(p); int len=strlen(p); if(len>0){ DP(); print(0,len-1); } printf("\n"); if(T) printf("\n"); } return 0;}