hihocoder 1110 正则表达式

前端之家收集整理的这篇文章主要介绍了hihocoder 1110 正则表达式前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

#1110 : 正则表达式

时间限制: 1000ms
单点时限: 1000ms
内存限制: 256MB

描述

给定一个字符串,判断其是否为合法的正则表达式。

一个正则表达式定义为:

1:0是正则表达式,1也是正则表达式。

2:P和Q都是正则表达式,则PQ是正则表达式。

3:P是正则表达式,则(P)是正则表达式

4:P是正则表达式,则P*也是正则表达式

5:P和Q都是正则表达式,则P|Q是正则表达式。

输入

输入包含多组数据。

每组数据为一行一个字符串,长度不超过100。

输出

对于每组数据,如果输入是合法的正则表达式,输出yes,否则输出no。

样例输入
  1. 010101101*
  2. (11|0*)*
  3. )*111
样例输出
  1. yes
  2. yes
  3. no
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const int maxn = 105;
  6. int f[maxn][maxn];
  7. char s[maxn];
  8. bool dfs(int i,int j,int &p)
  9. {
  10. if(i>j) return false;
  11. if(s[i]=='*'||s[i]=='|'||s[i]==')') return false;
  12. for(;p<=j;p++)
  13. {
  14. if(s[p]=='*'||s[p]=='0'||s[p]=='1') continue;
  15. else if(s[p]=='(')
  16. {
  17. p++;
  18. if(dfs(p,j,p))
  19. {
  20. if(s[p]==')') continue;
  21. else return false;
  22. }
  23. return false;
  24. }
  25. else if(s[p]==')') return true;
  26. else if(s[p]=='|')
  27. {
  28. if(s[p+1]=='*'||s[p+1]=='|'||s[p+1]==')') return false;//这里有问题
  29. }
  30. else return false;
  31. }
  32. return true;
  33. }
  34. int main()
  35. {
  36. // freopen("in.txt","r",stdin);
  37. while(~scanf("%s",s))
  38. {
  39. memset(f,-1,sizeof(f));
  40. int len=strlen(s);
  41. int k=0;
  42. bool ans=dfs(0,len-1,k);
  43. if(k<len-1) ans=false;
  44. if(ans)
  45. printf("yes\n");
  46. else printf("no\n");
  47. }
  48. return 0;
  49. }

这一题我和网上一些人的思路不一样,刚开始我以为用我这个方法会有很多特例,所以这一题拖了数月,今天稍微有点闲,便试了一下,发现还好(其实是数据比较弱),不是很复杂。

猜你在找的正则表达式相关文章