带通配符的字符串匹配

求这道题的函数递归c++写法
题目 -  带通配符的字符串匹配   
 
来源 计算概论A 2011 
描述 
通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。 

你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。 

例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456； 
2*77?8可以匹配 24457798、237708、27798。
 
关于输入 
输入有两行，每行为一个不超过20个字符的字符串，第一行带通配符，第二行不带通配符
 
关于输出 
如果两者可以匹配，就输出“matched”，否则输出“not matched”
 
例子输入 
1*456?

11111114567
 
例子输出 
matched
 

9 个解决方案

#1

急求 多谢

#2

仅供参考

//摘自《代码之美》
// 字符     含义
// .        匹配任意的单个字符
// ^        匹配输入字符串的开头
// $        匹配输入字符串的结尾
// *        匹配前一个字符的零个或者多个出现
#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)

#3

自己测了一下，暂时没有发现问题，可以看看，发现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;
}
}
}

#4

这是我自己编的一个函数,但是总有小情况,能帮忙检查一下发生什么问题了么
#include<iostream>
#include<string.h>
using namespace std;
bool match(char *a,char *b)
{
     if(*a=='?'||*a==*b)
         return match(a+1,b+1);
     if(*a=='*')
     {
         while(*b!='\0')
         {
         if(match(a+1,b++))
            return 1;
         }
     }
     if(*a=='\0')
        return *a==*b;
     return 0;
}
int main(){
    char a[20]={0},b[20]={0};
    cin>>a>>b;
    cout<<(match(a,b)==1?"matched":"not matched")<<endl;
}

#5

求大牛帮助..........

#6

现在问题如下
输入123*  123
输出为not matched   
为什么???
#include<iostream>
#include<string.h>
using namespace std;
bool match(char *a,char *b)
{
     if(*a=='\0')
     {
           if(*b=='\0')
           return 1;
           else 
           return 0;      
     }
     else if(*b=='\0')
     return 0;
     if(*a=='?'||*a==*b)
     return match(a+1,b+1);
     if(*a=='*')
     {
     while(*b!='\0')
     {
     if(match(a+1,b++))
      return 1;
     }
     if(*(a+1)=='\0'&&*b=='\0')
     return 1;
     }
     return 0;
}
int main(){
    char a[20]={0},b[20]={0};
    cin>>a>>b;
    cout<<(match(a,b)==1?"matched":"not matched")<<endl;
system("pause");
}

#7

 
#include "cstring"
#include "iostream"
using namespace std;

int main()
{   
     

     char a[21],b[21];    
 int la,lb,t,i;
     cin>>a>>b;
 la=strlen(a);
 lb=strlen(b);
 t=0;
 for(i=0;i<la;i++)
 {   
 if(b[t]=='\0' && a[i]!='*' )  {cout<<"not matched"<<endl; return 0;}
 if(a[i]=='?')  {t++;continue;}  
         if(a[i]=='*' && a[i+1]=='/0') {cout<<"matched"<<endl;  return 0;}
 if(a[i]=='*' && a[i+1]==b[t]) continue;

         if(a[i]=='*' && a[i+1]!=b[t])
 {
         while(1)
 {
         t++;
 if(a[i+1]==b[t] ) break;
 }
         continue;
 }
 if(a[i]!=b[t]) break;
 t++;
  
 }

     if(i<la  ) cout<<"not matched"<<endl;
 else cout<<"matched"<<endl;

 

  return 0;
}
 哪错了?

#8

引用 2 楼 zhao4zhong1 的回复:

仅供参考

//摘自《代码之美》
// 字符     含义
// .        匹配任意的单个字符
// ^        匹配输入字符串的开头
// $        匹配输入字符串的结尾
// *        匹配前一个字符的零个或者多个出现
#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)

老师，貌似开头是 * 的话就不能匹配了

#9

提醒：regex是开源的。