Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. 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.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Sample Input
1
([(]
Sample Output
()[()]
题意：将给出的括号序列以添加最小数目括号的形式进行配对
思路：利用动态规划解决
d[i][j]表示从i到j的范围内最少需要添加的括号数
pos[i][j]表示i到j的范围内从pos[i][j]处分开进行添加可使得括号数最小，为-1表示无需分开添加
若s[i]和s[j]组合为"()"或"[]",则说明已经配对，只需处理i和j内部的序列，且暂时令pos[i][j]=-1；
然后枚举i到j中的分界点，查看是否存在k使得d[i][j]>d[i][k]+d[k][j]（状态转移方程），若存在，
则说明将i和j从k处分离成两部分进行处理可使得添加的括号数更小，此时令pos[i][j]=k，记录下此分界点
show函数说明：利用递归输出匹配后的括号序列
1、如果i>j，越界，则返回
2、如果i==j，说明只处理的一个括号，输出对应的配对括号对即可
3、如果i<j，首先判断pos[i][j]?-1，若相等，说明i和j之间无需分解，
先输出左边，然后递归输出中间，最后输出右边括号；若不相等，则递归
输出i到pos[i][j]，pos[i][j]+1到j两部分
这一题如果只是求最少匹配括号还是蛮好写的。。初始化dp[i][i] = 1，如果区间两边相等，他的最少匹配等于里面的，然后枚举k的位置，求怎样划分会使整个区间最优。。因为要输出路径，所以要记下那个位置。。。打印用递归打印，又学了一招。。
递归输出代码还可以这样写
int match(char a,char b){
if((a=='('&&b==')')||(a=='['&&b==']'))return 1;
return 0;
}
char s[110];
void print(int i,int j)
{
if(i>j)
return;
if(i==j){
if(s[i]=='('||s[i]==')')printf("()");
else printf("[]");
return;
}
int ans=dp[i][j];
if(match(s[i],s[j])&&ans==dp[i+1][j-1]){
printf("%c",s[i]);
print(i+1,j-1);
printf("%c",s[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 ;
}
}
}
或者直接用一个pos【】【】记录最优位置
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 256;
int dp[maxn][maxn], pos[maxn][maxn];
char str[maxn];
void print_str(int i, int j)
{
if(i > j) return ;
if(i == j)
{
if(str[i] == '(' || str[j] == ')')
printf("()");
else
printf("[]");
}
if(i < j)
{
if(pos[i][j] == -1)
{
printf("%c", str[i]);
print_str(i+1, j-1);
printf("%c", str[j]);
}
else
{
print_str(i, pos[i][j]);
print_str(pos[i][j]+1, j);
}
}
}
int main()
{
int t;
scanf("%d", &t);
getchar();
while(t--)
{
gets(str);
gets(str);
memset(dp, 0, sizeof(dp)); //这里一定要赋值0。。。因为dp[i][j] = dp[i+1][j-1];，可能i+1 >= j了。。那样应该是0，而不是无穷大
memset(pos, -1, sizeof(pos));
int l = strlen(str);
for(int i = 0; i <= l; i++) dp[i][i] = 1; //如果只是自己的话，就只需要一个
for(int len = 1; len < l; len++)
{
for(int i = 0; i + len < l; i++)
{
int j = i + len;
dp[i][j] = 0x7fffffff;
if(str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']') //可以配对的话 最少的就是dp[i+1][j-1]
dp[i][j] = dp[i+1][j-1];
for(int k = i; k <= j; k++)
{
if(dp[i][j] > dp[i][k]+dp[k+1][j]) //在这里寻找最优位置匹配一个括号
{
dp[i][j] = dp[i][k] + dp[k+1][j];
pos[i][j] = k; //注意 每个区间只有一个最优的位置
}
}
}
}
print_str(0,l-1);
printf("\n");
if(t)
printf("\n");
}
return 0;
}