【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