带通配符的字符串匹配

码拜

9年 ago

求这道题的函数递归c++写法
题目 – 带通配符的字符串匹配

来源计算概论A 2011
描述
通配符是一类键盘字符，当我们不知道真正字符或不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。
你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们能否能够匹配。
例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456；
2*77?8可以匹配 24457798、237708、27798。

关于输入
输入有两行，每行为一个不超过20个字符的字符串，第一行带通配符，第二行不带通配符

关于输出
假如两者可以匹配，就输出“matched”，否则输出“not matched”

例子输入
1*456?
11111114567

例子输出
matched

仅供参考

//摘自《代码之美》
// 字符     含义
// .        匹配任意的单个字符
// ^        匹配输入字符串的开头
// $        匹配输入字符串的结尾
// *        匹配前一个字符的零个或多个出现
#include <stdio.h>
int matchhere(char *regexp, char *text);
int matchstar(int c, char *regexp, char *text) {// matchstar: search for c*regexp at beginning of text
   do {// a * matches zero or more instances
       if (matchhere(regexp, text)) return 1;
   } while (*text != ""\0"" && (*text++ == c || c == "".""));
   return 0;
}
int matchhere(char *regexp, char *text) {// matchhere: search for regexp at beginning of text
   if (regexp[0] == ""\0"") return 1;
   if (regexp[1] == ""*"") return matchstar(regexp[0], regexp+2, text);
   if (regexp[0] == ""$"" && regexp[1] == ""\0"") return *text == ""\0"";
   if (*text!=""\0"" && (regexp[0]==""."" || regexp[0]==*text)) return matchhere(regexp+1, text+1);
   return 0;
}
int match(char *regexp, char *text) {// match: search for regexp anywhere in text
    if (regexp[0] == ""^"") return matchhere(regexp+1, text);
    do {// must look even if string is empty
        if (matchhere(regexp, text)) return 1;
    } while (*text++ != ""\0"");
    return 0;
}
void main() {
    printf("%d==match(abc ,abc)\n",match("abc" ,"abc"));
    printf("%d==match(^a  ,abc)\n",match("^a"  ,"abc"));
    printf("%d==match(c$  ,abc)\n",match("c$"  ,"abc"));
    printf("%d==match(a.c ,abc)\n",match("a.c" ,"abc"));
    printf("%d==match(a.*c,abc)\n",match("a.*c","abc"));
    printf("--\n");
    printf("%d==match(ABC ,abc)\n",match("ABC" ,"abc"));
    printf("%d==match(^B  ,abc)\n",match("^B"  ,"abc"));
    printf("%d==match(A$  ,abc)\n",match("A$"  ,"abc"));
    printf("%d==match(a..c,abc)\n",match("a..c","abc"));
    printf("%d==match(a.*d,abc)\n",match("a.*d","abc"));
}
//1==match(abc ,abc)
//1==match(^a  ,abc)
//1==match(c$  ,abc)
//1==match(a.c ,abc)
//1==match(a.*c,abc)
//--
//0==match(ABC ,abc)
//0==match(^B  ,abc)
//0==match(A$  ,abc)
//0==match(a..c,abc)
//0==match(a.*d,abc)

本人测了一下，暂时没有发现问题，可以看看，发现BUG可以告诉本人，一起学习
void CompareStr(char *strone, char *strtwo)
{
if(strone[0] == “”\0″” || strtwo[0] == “”\0″”)
{
if(strone[0] == strtwo[0])
{
cout << “matched” << endl;
}
else
{
cout << “not matched” << endl;
}
return;
}
if(strone[0] == strtwo[0])
{
if(strone[1] == “”\0″” && strtwo[1] != “”\0″”)
{
CompareStr(strone, strtwo+1);
}
else
{
CompareStr(strone+1, strtwo+1);
}
}
else
{
if(strone[0] == “”?””)
{
CompareStr(strone+1, strtwo+1);
}
else if(strone[0] == “”*””)
{
int i = 0;
while (strtwo[i] != “”\0″” && strtwo[i] != strone[1])
{
i++;
}
if(strtwo[i] == “”\0″”)
{
cout << “not matched” << endl;
return;
}
CompareStr(strone+1, strtwo+i);
}
else
{
CompareStr(strone, strtwo+1);
return;
}
}
}