题目链接：http://hihocoder.com/problemset/problem/1110

题目分析：典型区间dp题，和括号匹配做法类似，设dp[i][j]为将区间i到j变成合法正则表达式所需要增添的最小字符数，显然若区间i到j合法则有dp[i][j] == 0，初始状态若s[i]为'0'或'1'，则dp[i][i] = 0，否则为无穷大，然后枚举长度进行区间dp，对于五个定义，定义1用来做上述初始化，定义2和5是一类，需要枚举分割点，若区间内不存在'|'，则用定义2，否则用定义5；定义3和4是一类，直接判断即可，定义3若括号内的是合法的则加上括号也合法，定义4若dp[i][j - 1]合法，加一个'*'也合法，最后判断dp[0][len - 1]是否为0即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 105;
int const INF = 0x3fffffff;
char s[MAX];
int dp[MAX][MAX];

int main()
{
    while(scanf("%s",s) != EOF)
    {
        int len = strlen(s);
        for(int i = 0; i < len; i++)
            for(int j = 0; j < len; j++)
                dp[i][j] = INF;
        for(int i = 0; i < len; i++)
            if(s[i] == '0' || s[i] == '1')
                dp[i][i] = 0;
        for(int l = 1; l < len; l++)
        {
            for(int i = 0; i < len - l; i++)
            {
                int j = i + l;
                if((s[i] == '(' && s[j] == ')') && dp[i + 1][j - 1] == 0)
                    dp[i][j] = 0;
                if(s[j] == '*' && dp[i][j - 1] == 0)
                    dp[i][j] = 0;
                for(int k = i; k < j; k++)
                {
                    if(dp[i][k] == 0 && dp[k + 1][j] == 0)
                        dp[i][j] = 0;
                    if(s[k] == '|' && k > 0 && dp[i][k - 1] == 0 && dp[k + 1][j] == 0)
                        dp[i][j] = 0;
                }     
            }
        }
        printf("%s\n",dp[0][len - 1] ? "no" : "yes");
    }
}