Question

用C语言完成一个正则表达式的匹配： 字符串中只有*和？是可变字符且位置和个数不固定，其他的字符位置固定

*代表任意个任意的字符
？代表一个任意的字符
例如:字符串为 mad*se$?243*.xml
其中*代表有任意个任意字符
?代表有一个任意字符，而其他位置的字符不变。
字符串madewfse$a?243rt.xml与源字符串相匹配。
字符串padewfse$a?243rt.xml与源字符串不匹配。

Answer 1

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
//1、'?'很好处理，只要在原有的定位函数中加一点点就行：
int index(char *s,char *t,int pos)
{
int i=pos,j=0,lens=strlen(s),lent=strlen(t);
while(i<lens&&j<lent)
{
if(s[i]==t[j]||t[j]=='?')
{
++i;
++j;
}
else
{
i=i-j+1;
j=0;
}
}
if(j==lent)return i-lent;
else return -1;
}
/*2、'*'的处理有些麻烦，很自然的想法是'*'把整个T串分成若干不含'*'的子串，
拿这些子串依次匹配S串。
按这样的方法可以把S串分成两类：
A、T=T1*T2*...Tn*，其中Ti为不含'*'的子串，且不为空（T1可为空）。
B、T=T1*T2*...Tn
二者的差别只在于尾部是否有'*'。
拿T匹配S，
首先 T1匹配S头部，index(s,t1,0)==0
然后 用循环完成后面的匹配，从前一次匹配后的末尾位置开始向后匹配，
如果匹配成功再把末尾位置记录下来。这里只用了最左匹配，为什么就足够了呢？
比如实际中的情况T1串可能在S串不止出现一次，为什么只考虑最左一个呢？
因为整个匹配过程是从左向右，最左匹配可以保证余下的S子中最长，更有利于后面T子串的匹配成功，
试想如果T1最左匹配不成功，靠右一些有可能成功吗？
例：T="*is*a*" S="this is a program"
T 子串"is"在S中有出现两个位置，匹配的时候只需要考虑最左边那个"is"就行了，
因为最左边的"is"匹配成功后，余下的S子串是" is a program"，余下的T子串是"*a"，
最左匹配可使余下的S子串最长，匹配的可能最大，最容易匹配的情况已经验证了，
就不用再做无用功了。
*/
int match(char *s,char *t)
{
int i=0,j=0,lens=strlen(s),lent=strlen(t);
char buf[128];
int bufp=0;
while(j<lent&&t[j]!='*')
{
buf[bufp]=t[j];
++bufp;++j;
}
buf[bufp]='\0';
if(index(s,buf,0)!=0)return 0;
i=bufp;
while(1)
{
while(j<lent&&t[j]=='*')++j;
if(j==lent)return 1;
bufp=0;
while(j<lent&&t[j]!='*')
{
buf[bufp]=t[j];
++bufp;++j;
}
buf[bufp]='\0';
if(j==lent)
{
if(index(s,buf,i)!=lens-bufp)return 0;
return 1;
}
if((i=index(s,buf,i))==-1)return 0;
i+=bufp;
}

}
void main()
{
char s[128];
char t[128]="mad*se$?243*.xml";

memset(s,'\0',128);//初始化s
printf("输入字符串,进行匹配\n");
gets(s);

if(match(s,t))
printf("匹配\n");
else
printf("不匹配\n");

}

Answer 2

遇到?号，直接匹配一个字符，遇到*号，跳到下一个，找和下一个匹配的位置为止，自己体会

Answer 3

遇到?号，直接匹配一个字符，遇到*号，跳到下一个，找和下一个匹配的位置为止，自己体会