题意：给出一串由‘（‘）’‘ [ ’ ’ ] ‘组成的串，让你输出添加最少括号之后使得括号匹配的串。
分析：那么假如我们知道任意 i 到 j 从哪儿插入分点使得匹配添加括号最少。那么我们定义ans[i][j]表示 i 到 j 从哪儿分开使得匹配添加括号最少，如果i和j匹配我们可以让ans[i][j] = -1；

我们发现在我们之前更新dp[ i ] [ j ] 的时候如果中间点k使得if ( dp [ i ] [ d] + dp [ d+1 ] [ j ] >= dp [ i ] [ j ] ) ，那么我们从d分开可以让添加的括号最少。

最后我们递归输出路径即可，还要注意((((这种情况要考虑到。

代码如下：

//
//Created by BLUEBUFF 2016/1/10
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 210;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head

char s[maxn];
int dp[maxn][maxn], ans[maxn][maxn];

void dfs(int l, int r)
{
    if(l > r) return ;
    if(l == r){
        if(s[l] == '(' || s[l] == ')') printf("()");
        else printf("[]");
    }
    else{
        if(ans[l][r] == -1){
            printf("%c", s[l]);
            dfs(l + 1, r - 1);
            printf("%c", s[r]);
        }
        else{
            dfs(l, ans[l][r]);
            dfs(ans[l][r] + 1, r);
        }
    }
}

int main()
{
    while(gets(s))
    {
        CLR(dp, 0);
        int le = strlen(s);
        for(int len = 1; len < le; len++){
            for(int i = 0; i + len < le; i++){
                int j = i + len;
                if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']'){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                    ans[i][j] = -1;
                }
                for(int d = i; d < j; d++){
                    if(dp[i][d] + dp[d+1][j] >= dp[i][j]){
                        dp[i][j] = dp[i][d] + dp[d + 1][j];
                        ans[i][j] = d;
                    }
                }
            }
        }
        dfs(0, le - 1);
        printf("\n");
    }
    return 0;
}