//输出最优括号匹配 dp #include <iostream> #include <string> using namespace std; string &operator+(string a,string b) { a.append(b); return a; } string dp[101][101]; string brackets; int main() { string maxstr = ""; int maxl = 250; for( int i = 0; i < maxl; i++ ) maxstr = maxstr + "a"; cin>>brackets; int l = brackets.length(); for( int i = 1;i <= l;i++ ) dp[i][i-1] = ""; for( int i = 1;i <= l;i++ ) { string str = " "; str[0] = brackets[i-1]; if( brackets[i-1] == '(' ) dp[i][i] = str + ")"; if( brackets[i-1] == ')' ) dp[i][i] = "(" + str; if( brackets[i-1] == '[' ) dp[i][i] = str + "]"; if( brackets[i-1] == ']' ) dp[i][i] = "[" + str; } for( int leng = 1;leng <= l-1;leng++ ) { for( int i = 1;i + leng <= l;i++ ) { int j = i+leng; dp[i][j] = maxstr; if( brackets[i-1] == '(' && brackets[i+leng-1] == ')' || brackets[i-1] == '[' && brackets[i+leng-1] == ']' ) { if( brackets[i-1] == '(' ) dp[i][j] = "("+dp[i+1][j-1]+")"; else dp[i][j] = "["+dp[i+1][j-1]+"]"; } for( int k = i;k <= j-1;k++ ) { if( dp[i][j].length() > dp[i][k].length() + dp[k+1][j].length() ) { dp[i][j] = dp[i][k]; //这里直接 + 出错。。不知道为什么C++的重载哎 dp[i][j].append(dp[k+1][j]); } } } } cout<<dp[1][l]<<endl; }