hihoCoder挑战赛7 1001 正则表达式 （区间DP)
发布时间：2020-12-13 22:33:09 所属栏目：百科 来源：网络整理
导读：http://hihocoder.com/contest/challenge7/problem/1 描述 给定一个字符串，判断其是否为合法的正则表达式。 一个正则表达式定义为： 1：0是正则表达式，1也是正则表达式。 2：P和Q都是正则表达式，则PQ是正则表达式。 3：P是正则表达式，则(P)是正则表达式
|
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。 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("yesn");
else
printf("non");
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |