首页 > 代码库 > 水了两道括号匹配

水了两道括号匹配

POJ 1141

给一段括号序列,要求增加最少的括号,使之合法,输出序列。

dp[i][j]表示使给定序列的i到j成为合法序列所需添加的最少括号数,dp[0][length-1]即是答案,转移的话,如果s[i]和s[j]可以匹配那么dp[i][j] = dp[i+1][j-1],否则就考虑在中间选择一个位置m,使分割成的两个序列各自成为合法序列。方案的话就是多开一个数组记录然后递归输出。状态是从长度小的序列转移到长度长的序列,所以两层循环,外层枚举长度,内层枚举头位置即可。写成记忆化搜索简单一点,就是稍微慢些。

代码有点磨叽。

  1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 using namespace std;  5   6   7 char s[200];  8 char mat[300];  9 int d[200][200], g[200][200]; 10 bool pre[300], nex[300]; 11 bool match(int a, int b, char s[]) 12 { 13     if (s[a] == ( && s[b] == )) return true; 14     if (s[a] == { && s[b] == }) return true; 15     if (s[a] == [ && s[b] == ]) return true; 16     return false; 17 } 18 void output(int l, int r) 19 { 20     if (l > r) return; 21     if (g[l][r] == 0){ 22         printf("%c", s[l]); 23         output(l+1, r-1); 24         printf("%c", s[r]); 25     } 26     else if (g[l][r] == -1){ 27         if (pre[s[l]]) 28             printf("%c%c", s[l], mat[s[l]]); 29         else 30             printf("%c%c", mat[s[l]], s[l]); 31         output(l+1, r); 32     } 33     else if (g[l][r] == -2){ 34         output(l, r-1); 35         if (pre[s[r]]) 36             printf("%c%c", s[r], mat[s[r]]); 37         else 38             printf("%c%c", mat[s[r]], s[r]); 39     } 40     else if (g[l][r] == -3){ 41         printf("%c%c", s[l], s[r]); 42     } 43     else{ 44         output(l, g[l][r]); 45         output(g[l][r]+1, r); 46     } 47 } 48 int main() 49 { 50     memset(pre, false, sizeof(pre)); 51     memset(nex, false, sizeof(nex)); 52     pre[(] = 1; pre[{] = 1; pre[[] = 1; 53     nex[)] = 1; nex[}] = 1; nex[]] = 1; 54     mat[(] = ); mat[)] = (; 55     mat[{] = }; mat[}] = {; 56     mat[[] = ]; mat[]] = [; 57     while(gets(s)) 58     { 59         memset(d, 127, sizeof(d)); 60         int len = strlen(s); 61         for (int i = 0; i < len; i++){ 62             d[i][i] = 1; 63             g[i][i] = -1; 64         } 65         for (int i = 0; i < len-1; i++) 66             if (match(i, i+1, s)){ 67                 d[i][i+1] = 0; 68                 g[i][i+1] = -3; 69             } 70         for (int k = 1; k < len; k++) 71             for (int i = 0; i < len; i++){ 72                 int j = i + k; 73                 if (j >= len) break; 74                 int tmp = d[i+1][j-1];// + 2 * (1 - match(i, j, s)); 75                 if (match(i, j, s) && tmp < d[i][j]){ 76                     d[i][j] = tmp; 77                     g[i][j] = 0; 78                 } 79                 tmp = d[i+1][j]+1; 80                 if (tmp < d[i][j]){ 81                     d[i][j] = tmp; 82                     g[i][j] = -1; 83                 } 84                 tmp = d[i][j-1]+1; 85                 if (tmp < d[i][j]){ 86                     d[i][j] = tmp; 87                     g[i][j] = -2;  88                 } 89                 for (int m = i; m < j; m++){ 90                     tmp = d[i][m] + d[m+1][j]; 91                     if (tmp < d[i][j]){ 92                         d[i][j] = tmp; 93                         g[i][j] = m; 94                     } 95                 } 96             } 97 //        for (int i = 0; i < len; i++) 98 //            for (int j = i; j < len; j++) 99 //                printf("%d %d %d\n", i, j, d[i][j]);100     //    printf("%d\n", d[0][len-1]);    101         output(0, len-1);102         printf("\n");103     }104     return 0;105 }

 

TC SRM 628 DIV 2 500 Points

给一段括号序列,其中还有不超过5个通配符,问是否合法。

因为通配符不超过5个,所以可以直接枚举其可能(6的5次方),然后用栈来判断,如果是前括号则压入栈,如果是后括号则和栈顶匹配,可以弹出栈顶,否则矛盾退出。或者也是和上题一样的dp思路,最后看如果最少增加括号为0,即是合法。

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<string> 5 using namespace std; 6  7 int d[200][200]; 8 bool match(int a, int b, string s) 9 {10     if (s[a] == X)11         if (s[b] == } || s[b] == ) || s[b] == ] || s[b] == X) return true;12     if (s[b] == X)13         if (s[a] == ( || s[a] == { || s[a] == [ || s[a] == X) return true;14     if (s[a] == ( && s[b] == )) return true;15     if (s[a] == { && s[b] == }) return true;16     if (s[a] == [ && s[b] == ]) return true;17     return false;18 }19 20 class BracketExpressions{21 public:22     string ifPossible(string s)23     {    24         int len = s.length();25         for (int i = 0; i < len; i++)26             d[i][i] = 1;27         for (int i = 0; i < len-1; i++) if (match(i, i+1, s))28             d[i][i+1] = 0;29         for (int k = 1; k < len; k++)30             for (int i = 0; i < len; i++){31                 int j = i + k;32                 if (j >= len) break;33                 d[i][j] = 214748360;34                 if (match(i, j, s))35                     d[i][j] = d[i+1][j-1];36                 for (int m = i; m < j; m++)37                     d[i][j] = min(d[i][j], d[i][m] + d[m+1][j]);38             }39         if (d[0][len-1] == 0) return "possible";40         else return "impossible";41     }42 }