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.For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
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 a1 a2 … an is called a subsequence of the string b1 b2 … bm, if there exist such indices 1 = i1 < i2 < … < in = m, that aj = bij for all 1 = j = n. Input The input file contains at most 100 brackets (characters ‘(‘, ‘)’, ‘[’ and ‘]’) that are situated on a single line without any other characters among them. Output 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 ([(] Sample Output ()[()]
转载：http://blog.csdn.net/lijiecsu/article/details/7589877
题目描述：
定义合法的括号序列如下：
1 空序列是一个合法的序列
2 如果S是合法的序列，则(S)和[S]也是合法的序列
3 如果A和B是合法的序列，则AB也是合法的序列
例如：下面的都是合法的括号序列
(), [], (()), ([]), ()[], ()[()]
下面的都是非法的括号序列
(, [, ), )(, ([)], ([(]
给定一个由’(‘, ‘)’, ‘[‘, 和 ‘]’ 组成的序列，找出以该序列为子序列的最短合法序列。
解题思路：
根据“黑书”的思路，定义：
d[i][j]为输入序列从下标i到下标j最少需要加多少括号才能成为合法序列。0<=i<=j
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int d[1010][1010]; int c[1010][1010]; string s; int len; void dp()//这里dp的作用仅为确定插入位置，也可以说是分段的位置。 { for(int i=0;i<len;i++) d[i][i]=1; //一开始所有的单位区间需要添加的括号数为1 for(int l=1;l<len;l++) { for(int i=0;i+l<len;i++) { int j=i+l; d[i][j]=d[i+1][j]+d[i][i]; //根据小区间转移 c[i][j]=i; //一开始默认分段位置为i 即把i和i+,j段切开 for(int k=i+1;k<j;k++) { if(d[i][k]+d[k+1][j]<d[i][j]) //枚举分段的位置，如果比在第一位添加的括号少，替换 { d[i][j]=d[i][k]+d[k+1][j]; c[i][j]=k;//更新分段位置 } } if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']') { if(d[i][j]>d[i+1][j-1])//如果这个区间是相互对应的，它会有多一种选择就是，直接取i+1，j-1 区间的结果 { d[i][j]=d[i+1][j-1]; c[i][j]=-1; //这样是没有需要切断的位置。 } } } } } void print(int i,int j) { if(i>j) return ; if(i==j) { if(s[i]=='('||s[i]==')') printf("()"); else printf("[]" ); } else { if(c[i][j]>=0) { print(i,c[i][j]); print(c[i][j]+1,j); } else { if(s[i]=='(') { cout<<"("; print(i+1,j-1); cout<<")"; } else { cout<<"["; print(i+1,j-1); cout<<"]"; } } } } int main() { cin>>s; len=s.size(); dp(); print(0,len-1); cout<<endl; return 0; }