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;
- }