经典DP问题，注意输入不要使用while(xxx != EOF)，否则WA，测试数据只有一组。同样的测试数据可能有多种答案。但最小长度唯一。一定不能用while，切记。
#include <iostream>
using namespace std;
#include <string> #define MAXNUM 200
#define MAXVAL 32767 string match(char []); int main() {
string regstr;
char str[MAXNUM]; cin >>str;
regstr = match(str);
cout <<regstr<<endl; return ;
} string match(char str[]) {
string regstr[MAXNUM][MAXNUM];
int add[MAXNUM][MAXNUM];
int len = strlen(str);
int i, j, k; memset(add, , sizeof(add)); for (i=; i<len; i++)
for (j=i; j<len; j++)
{
add[i][j] = MAXVAL;
regstr[i][j] = "";
} for (i=len-; i>=; i--) {
for (j=i; j<len; j++) {
if (j == i) {
add[i][j] = ;
if (str[i] == '(' || str[i] == ')')
regstr[i][j] = "()";
if (str[i] == '[' || str[i] == ']')
regstr[i][j] = "[]";
} else {if (str[i] == '(' && str[j] == ')') {
add[i][j] = add[i+][j-];
regstr[i][j] = "(" + regstr[i+][j-] + ")";
} else if (str[i] == '[' && str[j] == ']') {
add[i][j] = add[i+][j-];
regstr[i][j] = "[" + regstr[i+][j-] + "]";
} for (k=i; k<j; k++) {
if (add[i][k]+add[k+][j] < add[i][j]) {
add[i][j] = add[i][k] + add[k+][j];
regstr[i][j] = regstr[i][k] + regstr[k+][j];
}
}
}
}
} return regstr[][len-];
}