DP_括号匹配序列问题

括号匹配问题

简单括号匹配问题是给出字符串，判断字符串中的括号是否匹配，此类问题核心解决方案就是利用栈的后进先出的特性，从左到右依次遍历字符串，遇左括号进栈，遇右括号将其与栈顶元素配对，若能配对，则栈顶元素出栈，继续遍历，若不能配对，则返回false。字符串遍历结束后，判断栈是否为空，若不为空返回false，若为空，返回true。以下有c和c++实现代码，用c++可以利用标准库提供的顺序容器适配器stack来实现栈结构，c语言则需要自己写栈结构，当然也可以用数组模拟栈结构，用一变量存放数组中最后面的元素的下标代表栈顶指针进行入栈出栈就可以了。

c语言版题目来自http://nyoj.top/problem/2

  1 /* 
  2 现在有一行括号序列，请你检查这行括号是否配对
  3 输入
  4 第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，
  5 每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。
  6 数据保证S中只含有"[", "]", "(", ")" 四种字符
  7 输出
  8 每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No
  9 实现：
 10 栈模型实现
 11 */
 12 #include<stdio.h>
 13 #include<stdlib.h>
 14 #include<stdbool.h>
 15 
 16 typedef struct Node * PNODE;
 17 
 18 struct Node
 19 {
 20     char data;
 21     PNODE pNext;
 22 }NODE;
 23 
 24 typedef struct Stack
 25 {
 26     PNODE pTop; //永远指向栈顶元素
 27     PNODE pBottom; //永远指向栈顶元素的下一个元素
 28 }STACK,* PSTACK;
 29 
 30 /* 建立空栈 */
 31 void InitStack(PSTACK pS)
 32 {
 33     pS->pTop = (PNODE)malloc(sizeof(NODE)); //头节点
 34     pS->pBottom = pS->pTop;
 35     pS->pTop->pNext = NULL; //将头节点指针域变成空的
 36 }
 37 
 38 /* 进行压栈 */
 39 void PushStack(PSTACK pS,char Str)
 40 {
 41     PNODE pNew = (PNODE)malloc(sizeof(NODE));//建立新节点
 42     pNew->data = Str; //存储数据
 43     pNew->pNext = pS->pTop; //将新节点进行压栈，头进头出
 44     pS->pTop = pNew; //将头节点指向新节点
 45 }
 46 /* 进行出栈 */
 47 char PopStack(PSTACK pS)
 48 {
 49     PNODE p = pS->pTop; //缓存出栈的节点地址
 50     char str = p->data; //缓存出栈的节点数据
 51     
 52     pS->pTop = p->pNext;//将栈顶往后移
 53     free(p);//将出栈节点销毁
 54     return str; //将出栈节点数据返回
 55 }
 56 /* 判断栈是否为空*/
 57 bool empty(PSTACK pS)
 58 {
 59     if(pS->pTop == pS->pBottom)
 60         return true;
 61     else
 62         return false;
 63 }
 64     
 65 /* 扫描字符串 */
 66 bool scanner(char * pStr)
 67 {
 68     STACK S;
 69     int i = 0;
 70     bool ret = true;
 71 
 72     InitStack(&S);
 73     while(*(pStr+i) != '')
 74     {
 75         switch(*(pStr+i))
 76         {
 77             case '(':
 78                 PushStack(&S,*(pStr+i));
 79                 break;
 80             case '[':
 81                 PushStack(&S,*(pStr+i));
 82                 break;
 83             case ')':
 84                 if(empty(&S))//如果栈已为空
 85                 {
 86                     return false;
 87                 }
 88                 ret = (PopStack(&S) == '(');
 89                 if(ret == false)
 90                 {
 91                     return ret;
 92                 }
 93                 break;
 94             case ']':
 95                 if(empty(&S))
 96                 {
 97                     return false;
 98                 }
 99                 ret = (PopStack(&S) == '[');
100                 if(ret == false)
101                 {
102                     return ret;
103                 }
104                 break;
105         }
106         i++;
107     }
108     if(empty(&S) == false) //如果扫描完字符串栈不是空的
109     {
110         ret = false;
111     }
112     return ret;
113 
114 }
115 
116 int main(void)
117 {
118     int n,ret;
119     char str[10005];
120     scanf("%d",&n);
121     getchar();
122     while(n--)
123     {
124         scanf("%s",str);
125         getchar();
126         if(scanner(str))
127         {
128             printf("Yes
");
129         }
130         else
131         {
132             printf("No
");
133         }
134     }
135 
136     return 0;
137 }

c语言实现

c++版题目来自http://codevs.cn/problem/2058/

 1 /*括号配对*/
 2 #include<iostream>
 3 #include<stack>
 4 #include<string>
 5 using namespace std;
 6 int main(void)
 7 {
 8     stack<char> my_stack;
 9     int n;
10     cin >> n;
11 
12     while(n--){
13         while( !my_stack.empty() ) //清空栈
14             my_stack.pop();
15         string t_str;
16         int k = 1;
17         string::iterator begin,end;
18 
19         cin >> t_str;
20         begin = t_str.begin();
21         end = t_str.end();
22         while(begin != end){
23             char t = *begin++;
24             if(t == '<' || t == '(' || t == '{' || t == '[')
25                 my_stack.push(t);
26             else{
27                 if(my_stack.empty()){
28                     cout << "FALSE" << endl;
29                     k = 0;
30                     break;
31                 }
32                 char tch = my_stack.top();
33                 if(t == '>' && tch != '<' ||
34                     t == '}' && tch != '{' ||
35                     t == ')' && tch != '(' ||
36                     t == ']' && tch != '['){
37                     cout << "FALSE" << endl;
38                     k = 0;
39                     break;
40                 }
41                 my_stack.pop();
42              }
43         }
44         if(k){
45             if(my_stack.size())
46                 cout << "FALSE" << endl;
47             else
48                 cout << "TRUE" <<endl;
49         }
50     }
51 
52     return 0;
53 }

c++实现

括号序列问题

此类问题给出一串由'(' ')' '[' ']' 四种字符组成的字符串，要求在字符串中添加若干个括号，使整个字符串达到匹配状态，这类问题属于区间动态规划问题，试想，题目要求的是整个字符串匹配的时候的最小的添加的括号的个数，我们定义两个指针变量i,j 分别指向字符串的头和尾，如果s[i]和s[j]匹配，那整个问题的解就是除了s[i]和s[j]后的子串s[i+1]到s[j-1]的解(代码第33行)，而子串的解又由更小的字串的解来确定，所以可以知道，此问题采用自底而上的解法，亦或者说成自小而大的解法。上面的过程也可称为问题的状态转移过程，在考虑完状态转移过程后还必须考虑边界问题，状态转移是由小串到大串，所以从右至左或从左至右都可以，但是要考虑边界问题，此问题中，边界问题就是只有一个字符的字串和空串，用i和j代表一前一后两个字符，那么只有一个字符时也就是i和j相等时候，此时,dp[i][j]，也就是dp[i][i]为1，当字串为空串时，也是i>j时候此时 dp[i][j]为0 也可作dp[i+1][i]为0.由此想来，得是从右至左处理字符串方便。在程序中，需要将每个子串的最优解存起来，所以有数组dp[i][j]存储从i到j的这个字串的最优解是多少。

题目自 http://nyoj.top/problem/15

#include<bits/stdc++.h>
using namespace std;

int d[101][101];

bool match(char a, char b) {
    // i肯定在j前面，所以a肯定得是左括号，b肯定得是右括号 
    return (a == '(' && b == ')' ) ||
            (a == '[' && b == ']');
}

int main(void)
{
    int N;
    cin >> N;
    getchar();
    while(N--) {
        string s;
        getline(cin, s);
        int len = s.size();
        if( len == 0 ) {
            cout << 0 << endl;
            continue;
        }
        memset(d,0,sizeof(d));
        for(int i = 0; i < len; ++i) {
            d[i][i] = 1;
        } 
        
        for( int i = len -2; i >= 0; --i ) {
            for( int j = i + 1; j < len; ++j ) {
                d[i][j] = 0x3f3f3f3f; // 0x3f3f3f3f 代表无穷大，有意研究者可自行百度 
                if(match(s[i],s[j])) d[i][j] = d[i+1][j-1]; 
                for( int k = i; k < j; ++k ) {
                    d[i][j] = min(d[i][j],d[i][k]+d[k+1][j]);
                }
            }
        }
        
        cout << d[0][len-1] << endl;
    }
    
    return 0;
}

代码实现

总结

动态规划作为一种解决问题的思想，其主要手段就是存储子问题的最优解来导出整个问题的最优解，那么需要考虑的就是最小的子问题如果处置，也就是边界问题，还有就是子问题如何向整个问题迈进或者整个问题如何分成子问题来求解，如何利用子问题的解，和选择最优解，也就是状态转移问题。

长袍纸扇山羊须，凉菜花生小酒，岂不美哉！