hihocoder 1110 正则表达式

发布时间：2020-12-14 00:56:56 所属栏目：百科来源：网络整理

导读：#1110 : 正则表达式时间限制: 1000ms 单点时限: 1000ms 内存限制: 256MB 描述给定一个字符串，判断其是否为合法的正则表达式。一个正则表达式定义为： 1：0是正则表达式，1也是正则表达式。 2：P和Q都是正则表达式，则PQ是正则表达式。 3：P是正则表达式

#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。

样例输入

010101101*
(11|0*)*
)*111

样例输出

yes
yes
no

#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("yesn");
      else printf("non");
    }
    return 0;
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!