1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4  5 using namespace std ; 6  7 char sh[110] ; 8 int dp[110][110] ,mark[110][110] ; 9 //dp数组代表的是从i到j需要添加的最少的括号是多少，mark数组代表的是从i到j在mark[i][j]这个位置添加括号可以使得添加的括号数最少10 11 void print(int i,int j)12 {13     if(i > j) return  ;14     else if(i == j)15     {16         if(sh[i] == ‘(‘||sh[i] == ‘)‘)17                 printf("()") ;18         else printf("[]") ;19     }20     else if(mark[i][j] == -1)21     {22         printf("%c",sh[i]) ;23         print(i+1,j-1) ;24         printf("%c",sh[j]) ;25     }26     else27     {28         print(i,mark[i][j]) ;29         print(mark[i][j]+1,j) ;30     }31 }32 int main()33 {34     while(gets(sh))35     {36         int len = strlen(sh) ;37         memset(dp,0,sizeof(dp)) ;38         for(int i = 0 ; i < len ; i++)39         {40             dp[i][i] = 1 ;41         }42         for(int l = 1 ; l < len ; l ++)//从小区间推出大区间，枚举长度43         {44             int temp = len - l ;45             for(int i = 0 ; i < temp ; i++)46             {47                 int j = i + l ;48                 dp[i][j] = 99999999 ;49                 if((sh[i] == ‘(‘&& sh[j] == ‘)‘)|| (sh[i] == ‘[‘&&sh[j] == ‘]‘))50                 {51                     dp[i][j] = dp[i+1][j-1] ;52                     mark[i][j] = -1 ;53                 }54                 for(int k = i ; k < j ; k++)55                 {56                     int temp1 = dp[i][k] + dp[k+1][j] ;57                     if(dp[i][j] >= temp1)58                     {59                         dp[i][j] = temp1 ;60                         mark[i][j] = k ;61                     }62                 }63             }64         }65         print(0,len-1) ;66         puts("") ;67     }68     return 0 ;69 }