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

举报
王建峰 发表于 2021/11/19 00:23:15 2021/11/19
1.9k+ 0 0
【摘要】 《剑指Offer》面试题19:正则表达式匹配   1 题目 请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但与"a...

《剑指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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。