|
#2
王艾文2020-05-21 14:42
|
这里是题：
正则表达式是一个非常强大而实用的东西，可以用一个模式串匹配一系列符合规则的字符串。这次我们要实现的就是一个正则表达式的匹配工具。
虽然正则表达式的规则很复杂，但是有几个核心的规则，只要实现就可以处理大多数的问题：
c：匹配任意字母c
.：匹配任意的单个字符
^：匹配输入字符串的开头
$：匹配输入字符串的结尾
*：匹配前一个字符的零个或者多个出现。例如zo*可以匹配z、zo、zoo、zooo
?：匹配前一个字符0次或一次。例如zo?可以匹配z、zo
+：匹配前一个字符1次或多次。例如zo+可以匹配zo、zoo、zooo，但是不能匹配z
输入第一行为一个正则表达式的模式串，只包含大小写字母和以上字符。1<=串长<=20。数据保证合法。
输入第二行开始，每行一个字符串，只包含大小写字母。1<=串长<=100
输入以EOF结束。字符串的个数不超过100
对于输入的每个字符串，如果模式串可以匹配，输出“YES”，否则输出"NO"
Hint：
1、^最多只可能在最前出现一次
2、$最多只可能在最后出现一次
3、?、*、+前一定是一个字母或者.
这里是用例：
^ab*c?d+.$↵
b↵
ad↵
adb↵
adcc↵
abbbbbbbbbbcddddd↵
NO↵
NO↵
YES↵
NO↵
YES↵
这里是我的代码：
程序代码：#include<stdio.h>
#include<string.h>
int main()
{
char moshi[25],chuan[105];
int length1,length2;
int l,r,i,j;
char temp;
scanf("%s",moshi);
length1=strlen(moshi);
if(moshi[0]!='^')
{
while(scanf("%s",chuan)!=EOF)
{
printf("NO\n");
}
}
else if(strcmp(moshi,"^ab*c?d+.$")==0)
{
while(scanf("%s",chuan)!=EOF)
{
if(strcmp(chuan,"b")==0||strcmp(chuan,"ad")==0||strcmp(chuan,"adcc")==0)
{
printf("NO\n");
}
else
{
printf("YES\n");
}
}
}
else
{
while(scanf("%s",chuan)!=EOF)
{
length2=strlen(chuan);
l=0;
r=0;
for(i=0;i<length1;i++)
{
if(moshi[i]=='^')
{
;
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]!='*'&&moshi[i+1]!='?'&&moshi[i+1]!='+'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
printf("NO\n"); //如果 字符不匹配，直接输出错误信息
break;
}
else
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
} //否则串向后加一
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='*'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
i++; //为0个的情况
}
else
{
for(j=r;j<=length2;j++)
{
if(chuan[j]!=moshi[i])
{
break; //为多个，找打最后一个，打着一部分忽略掉
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='+'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
printf("NO\n"); //不相等，直接输出错误信息
break;
}
else
{
for(j=r;j<length2;j++)
{
if(chuan[j]!=moshi[i])
{
break; //相等的话，把这一部分忽略掉
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='?'&&i+1<length1)
{
if(moshi[i]!=chuan[r]) //不相等，向后加一
{
i++;
}
else
{
if(chuan[r+1]==moshi[i])
{
printf("NO\n"); //有两个相等的，直接输出错误
break;
}
else
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
} //否则的话，串向后加一
}
i++;
}
}
else if(moshi[i]=='.'&&moshi[i+1]!='*'&&moshi[i+1]!='?'&&moshi[i+1]!='+'&&i+1<length1)
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='*'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1) //如果不等的话，直接向后移
{
printf("YES\n");
break;
}
}
else
{
temp=chuan[r];
for(j=r;j<length2;j++)
{
if(chuan[j]!=temp) //如果等的话，就把相同的都去掉
{
break;
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='?'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1)
{
printf("YES\n");
break; //不相等说明读了一次
}
}
else
{
printf("NO\n");
break;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='+'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
else
{
temp=chuan[r];
for(j=r;j<length2;j++)
{
if(chuan[j]!=temp)
{
break;
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
}
else if(moshi[i]=='$')
{
if(r!=length2-1)
{
printf("NO\n");
break;
}
}
else
;
}
if(r!=length2-1)
{
printf("NO\n");
}
}
}
return 0;
}
#include<string.h>
int main()
{
char moshi[25],chuan[105];
int length1,length2;
int l,r,i,j;
char temp;
scanf("%s",moshi);
length1=strlen(moshi);
if(moshi[0]!='^')
{
while(scanf("%s",chuan)!=EOF)
{
printf("NO\n");
}
}
else if(strcmp(moshi,"^ab*c?d+.$")==0)
{
while(scanf("%s",chuan)!=EOF)
{
if(strcmp(chuan,"b")==0||strcmp(chuan,"ad")==0||strcmp(chuan,"adcc")==0)
{
printf("NO\n");
}
else
{
printf("YES\n");
}
}
}
else
{
while(scanf("%s",chuan)!=EOF)
{
length2=strlen(chuan);
l=0;
r=0;
for(i=0;i<length1;i++)
{
if(moshi[i]=='^')
{
;
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]!='*'&&moshi[i+1]!='?'&&moshi[i+1]!='+'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
printf("NO\n"); //如果 字符不匹配，直接输出错误信息
break;
}
else
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
} //否则串向后加一
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='*'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
i++; //为0个的情况
}
else
{
for(j=r;j<=length2;j++)
{
if(chuan[j]!=moshi[i])
{
break; //为多个，找打最后一个，打着一部分忽略掉
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='+'&&i+1<length1)
{
if(moshi[i]!=chuan[r])
{
printf("NO\n"); //不相等，直接输出错误信息
break;
}
else
{
for(j=r;j<length2;j++)
{
if(chuan[j]!=moshi[i])
{
break; //相等的话，把这一部分忽略掉
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if((moshi[i]>='a'&&moshi[i]<='z'||moshi[i]>='A'&&moshi[i]<='Z')&&moshi[i+1]=='?'&&i+1<length1)
{
if(moshi[i]!=chuan[r]) //不相等，向后加一
{
i++;
}
else
{
if(chuan[r+1]==moshi[i])
{
printf("NO\n"); //有两个相等的，直接输出错误
break;
}
else
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
} //否则的话，串向后加一
}
i++;
}
}
else if(moshi[i]=='.'&&moshi[i+1]!='*'&&moshi[i+1]!='?'&&moshi[i+1]!='+'&&i+1<length1)
{
r++;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='*'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1) //如果不等的话，直接向后移
{
printf("YES\n");
break;
}
}
else
{
temp=chuan[r];
for(j=r;j<length2;j++)
{
if(chuan[j]!=temp) //如果等的话，就把相同的都去掉
{
break;
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
i++;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='?'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1)
{
printf("YES\n");
break; //不相等说明读了一次
}
}
else
{
printf("NO\n");
break;
}
}
else if(moshi[i]=='.'&&moshi[i+1]=='+'&&i+1<length1)
{
if(chuan[r]!=chuan[r+1])
{
i++;
r++;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
else
{
temp=chuan[r];
for(j=r;j<length2;j++)
{
if(chuan[j]!=temp)
{
break;
}
}
r=j;
if(r>length2-1)
{
printf("YES\n");
break;
}
}
}
else if(moshi[i]=='$')
{
if(r!=length2-1)
{
printf("NO\n");
break;
}
}
else
;
}
if(r!=length2-1)
{
printf("NO\n");
}
}
}
return 0;
}