用C语言完成一个正则表达式的匹配： 字符串中只有*和？是可变字符且位置和个数不固定，其他的字符位置固定
#include #include #include //1、'?'很好处理，只要在原有的定位函数中加一点点就行： int index(char *s,char *t,int pos) { int i=pos,j=0,lens=strlen(s),lent=strlen(t); while(i { if(s[i]==t[j]||t[j]=='?') { i; j; } else { i=...全部
#include #include #include //1、'?'很好处理，只要在原有的定位函数中加一点点就行： int index(char *s,char *t,int pos) { int i=pos,j=0,lens=strlen(s),lent=strlen(t); while(i { 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 { buf[bufp]=t[j]; bufp; j; } buf[bufp]=' '; if(index(s,buf,0)!=0)return 0; i=bufp; while(1) { while(j if(j==lent)return 1; bufp=0; while(j { buf[bufp]=t[j]; bufp; j; } buf[bufp]=' '; 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,' ',128);//初始化s printf("输入字符串,进行匹配
"); gets(s); if(match(s,t)) printf("匹配
"); else printf("不匹配
"); }。
收起
