hihoCoder挑战赛7 1001 正则表达式 (区间DP)

前端之家收集整理的这篇文章主要介绍了hihoCoder挑战赛7 1001 正则表达式 (区间DP)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

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。

输出

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

样例输入
  1. 010101101*
  2. (11|0*)*
  3. )*111
样例输出
  1. yes
  2. yes
  3. no
  1. const int maxn=110;
  2. int dp[maxn][maxn];
  3. char s[maxn];
  4.  
  5. int main()
  6. {
  7. while(cin>>s)
  8. {
  9. int n=strlen(s);
  10. memset(dp,sizeof(dp));
  11. for(int i=0;i<n;i++)
  12. if(s[i]=='0'||s[i]=='1')
  13. dp[i][i]=1;
  14. for(int len=2;len<=n;len++)//枚举长度
  15. {
  16. for(int st=0;st+len-1<n;st++)//枚举起点
  17. {
  18. for(int mid=st+1;mid<=st+len-2;mid++)
  19. if(s[mid]=='|')
  20. dp[st][st+len-1]|=dp[st][mid-1]&&dp[mid+1][st+len-1];
  21. //起点是st,终点是st+len-1
  22. for(int mid=st;mid<=st+len-1;mid++)
  23. {
  24. dp[st][st+len-1]|=dp[st][mid]&&dp[mid+1][st+len-1];
  25. }
  26. if(s[st]=='('&&s[st+len-1]==')')
  27. dp[st][st+len-1]|=dp[st+1][st+len-2];
  28. if(s[st+len-1]=='*')
  29. dp[st][st+len-1]|=dp[st][st+len-2];
  30. }
  31. }
  32. if(dp[0][n-1])
  33. printf("yes\n");
  34. else
  35. printf("no\n");
  36. }
  37. return 0;
  38. }

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