【C/C++练习题】正则表达式匹配

《剑指Offer》面试题19：正则表达式匹配

1 题目

请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。

2 分析

掌握正则表达式的匹配规则。程序使用递归的方式对字符进行逐一匹配，直到匹配结束。在匹配过程中，'*'表示匹配它前面的字符可以出现任意次，可能会不匹配（匹配0次），或者尝试对重复字符进行匹配。

3 代码

  

   

    

     

    
    

     

      #include "iostream"
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：正则表达式匹配
     
    
   

    

     

    
    

     

      //规则：匹配字符，'.'表示任一字符， '*'表示上一个字符可重复任意次数(包括0次)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool Match_core(const char* src_str, const char* dest_str);
     
    
   

    

     

    
    

     

      bool Match(const char* src_str, const char* dest_str);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	cout << "Match(\"abc\", \"abc\") " << Match("abc", "abc") << endl;
     
    
   

    

     

    
    

     

      	cout << "Match(\"abc\", \"a.c\") " << Match("abc", "a.c") << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	cout << "Match(\"abc\", \"a*c\") " << Match("abc", "a*c") << endl;
     
    
   

    

     

    
    

     

      	cout << "Match(\"abbbc\", \"ab*c\") " << Match("abbbc", "ab*c") << endl;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	cout << "Match(\"abc\", \"ab.c\") " << Match("abc", "ab.c") << endl;
     
    
   

    

     

    
    

     

      	cout << "Match(\"\", \"abc\") " << Match("", "abc") << endl;
     
    
   

    

     

    
    

     

      	cout << "Match(\"abc\", \"\") " << Match("abc", "abc") << endl;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：正则表达式匹配字符串
     
    
   

    

     

    
    

     

      //输入：src_str 源字符地址， dest_str 模式字符地址
     
    
   

    

     

    
    

     

      //返回：false 匹配不成功， true 匹配成功
     
    
   

    

     

    
    

     

      bool Match(const char* src_str, const char* dest_str)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.判断参数的合法性
     
    
   

    

     

    
    

     
	if ( (NULL == src_str) || (NULL == dest_str) )
     
    
   

    

     

    
    

     
		return false;
     
    
   

    

     

    
    

     
	return Match_core(src_str, dest_str);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：正则表达式匹配字符串(递归方式)
     
    
   

    

     

    
    

     

      //输入：src_str 源字符地址， dest_str 模式字符地址
     
    
   

    

     

    
    

     

      //输出：false 匹配不成功， true 匹配成功
     
    
   

    

     

    
    

     

      bool Match_core(const char* src_str, const char* dest_str)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	//1.回归条件
     
    
   

    

     

    
    

     
	if ( (*src_str == '\0') && (*dest_str == '\0') )
     
    
   

    

     

    
    

     
		return true;
     
    
   

    

     

    
    

     
	if ( (*src_str != '\0') && (*dest_str == '\0') )
     
    
   

    

     

    
    

     
		return false;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//2.递推公式
     
    
   

    

     

    
    

     
	if ( *(dest_str+1) != '*')
     
    
   

    

     

    
    

     

      	{//下一个字符不是'*'
     
    
   

    

     

    
    

     
		if ( (*dest_str == *src_str) || (*dest_str == '.' && *src_str != '\0') )
     
    
   

    

     

    
    

     

      		{//当前字符匹配成功
     
    
   

    

     

    
    

     
			return Match_core(src_str+1, dest_str+1);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     
			return false;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     

      	{//下一个字符遇到'*'
     
    
   

    

     

    
    

     
		if ( (*dest_str == *src_str) || (*dest_str == '.' && *src_str != '\0') )
     
    
   

    

     

    
    

     

      		{//当前字符匹配成功
     
    
   

    

     

    
    

     
			//匹配规则：不匹配dest_str；重复匹配dest_str；(匹配一次)进行下一字符的匹配
     
    
   

    

     

    
    

     
			return Match_core(src_str, dest_str+2)
     
    
   

    

     

    
    

     

      				||	Match_core(src_str+1, dest_str)
     
    
   

    

     

    
    

     

      				||	Match_core(src_str+1, dest_str+2);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     
			//'*'设定为匹配0个字符
     
    
   

    

     

    
    

     
			return Match_core(src_str, dest_str+2);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98598911