http://hihocoder.com/contest/challenge7/problem/1
描述
给定一个字符串，判断其是否为合法的正则表达式。
一个正则表达式定义为：
1：0是正则表达式，1也是正则表达式。
2：P和Q都是正则表达式，则PQ是正则表达式。
3：P是正则表达式，则(P)是正则表达式
4：P是正则表达式，则P*也是正则表达式
5：P和Q都是正则表达式，则P|Q是正则表达式。
输入
输入包含多组数据。
每组数据为一行一个字符串，长度不超过100。
输出
010101101* (11|0*)* )*111样例输出
yes yes no
const int maxn=110;
int dp[maxn][maxn];
char s[maxn];
int main()
{
while(cin>>s)
{
int n=strlen(s);
memset(dp,sizeof(dp));
for(int i=0;i<n;i++)
if(s[i]=='0'||s[i]=='1')
dp[i][i]=1;
for(int len=2;len<=n;len++)//枚举长度
{
for(int st=0;st+len-1<n;st++)//枚举起点
{
for(int mid=st+1;mid<=st+len-2;mid++)
if(s[mid]=='|')
dp[st][st+len-1]|=dp[st][mid-1]&&dp[mid+1][st+len-1];
//起点是st,终点是st+len-1
for(int mid=st;mid<=st+len-1;mid++)
{
dp[st][st+len-1]|=dp[st][mid]&&dp[mid+1][st+len-1];
}
if(s[st]=='('&&s[st+len-1]==')')
dp[st][st+len-1]|=dp[st+1][st+len-2];
if(s[st+len-1]=='*')
dp[st][st+len-1]|=dp[st][st+len-2];
}
}
if(dp[0][n-1])
printf("yes\n");
else
printf("no\n");
}
return 0;
}
