#1110 : 正则表达式
时间限制:
1000ms
单点时限:
1000ms
内存限制:
256MB
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int maxn = 105;
- int f[maxn][maxn];
- char s[maxn];
- bool dfs(int i,int j,int &p)
- {
- if(i>j) return false;
- if(s[i]=='*'||s[i]=='|'||s[i]==')') return false;
- for(;p<=j;p++)
- {
- if(s[p]=='*'||s[p]=='0'||s[p]=='1') continue;
- else if(s[p]=='(')
- {
- p++;
- if(dfs(p,j,p))
- {
- if(s[p]==')') continue;
- else return false;
- }
- return false;
- }
- else if(s[p]==')') return true;
- else if(s[p]=='|')
- {
- if(s[p+1]=='*'||s[p+1]=='|'||s[p+1]==')') return false;//这里有问题
- }
- else return false;
- }
- return true;
- }
- int main()
- {
- // freopen("in.txt","r",stdin);
- while(~scanf("%s",s))
- {
- memset(f,-1,sizeof(f));
- int len=strlen(s);
- int k=0;
- bool ans=dfs(0,len-1,k);
- if(k<len-1) ans=false;
- if(ans)
- printf("yes\n");
- else printf("no\n");
- }
- return 0;
- }
这一题我和网上一些人的思路不一样,刚开始我以为用我这个方法会有很多特例,所以这一题拖了数月,今天稍微有点闲,便试了一下,发现还好(其实是数据比较弱),不是很复杂。