实现正则表达式匹配器
发布时间:2015-11-16 栏目:软件算法 评论:0 Comments
Rob Pike在《The Practice of Programming》中使用约30行代码,实现了一个正则表达式匹配器,用来处理以下的模型。
字符 | 含义 |
c | 匹配认字的字母c |
.(句点) | 匹配任意的单个字符 |
^ | 匹配输入字符串的开头 |
$ | 匹配输入字符串的结尾 |
* | 匹配前一个字符的零个或者多个出现 |
这段代码紧凑、优雅,高效并且实用,同时展示了C指针的强大功能。
/*match :在text中查找regexp*/
int match(char *regexp,char *text)
{
if(regexp[0] == ‘^’)
return matchhere(regexp+1,text);
do{ /*即使字符串为空也必须检查*/
if (matchhere(regexp,text))
return 1;
}while (*text++!= ‘\0’);
return 0;
}
int match(char *regexp,char *text)
{
if(regexp[0] == ‘^’)
return matchhere(regexp+1,text);
do{ /*即使字符串为空也必须检查*/
if (matchhere(regexp,text))
return 1;
}while (*text++!= ‘\0’);
return 0;
}
/*matchhere在text的开头查找regexp*/
int matchhere(char *regexp,char *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 matchhere(char *regexp,char *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;
}
/*matchstar :在text的开头查找C*regexp*/
int matchstar (int c,char *regexp,char *text)
{
do { /*通配符*匹配零个或多个实例*/
if (matchhere(regexp,text))
return 1;
}while (*text!=’\0′ && (*text++ ==c || c== ‘.’));
return 0;
}
int matchstar (int c,char *regexp,char *text)
{
do { /*通配符*匹配零个或多个实例*/
if (matchhere(regexp,text))
return 1;
}while (*text!=’\0′ && (*text++ ==c || c== ‘.’));
return 0;
}
以下是另外一个精简版本(主要区别为,去掉了首位符号检测、部分匹配功能以及‘*’单指匹配零个或者多个字符):
#include <stdio.h>
bool match(char* src, char* dst )
{
while( *src != ‘\0′ && (*src == *dst||*dst==’?’ )) src++, dst++;
if( *src == ‘\0’ && *dst == ‘\0’ ) return true;
if( *dst == ‘*’ )
{
for( ; *src != ‘\0’; src++ )
if( match( src, dst+1 ) )
return true;
}
return false;
}
int main(int agrv, char* argc[])
{
char data[]=”abcdef”;
char pattern[]=”a*c”;
bool result = match(data,pattern);
if(result==true)
printf(“Matched\n”);
else
printf(“Failed\n”);
return 0;
}
第一个版本功能更加强大也更通用,第二种版本比较简单。
让我还有点不太明白的是:这个实现方式并没有使用NFA或者DFA,那么这种方法跟NFA的实现方式的主要区别在哪里?时间复杂度更高么?
留下评论
You must be logged in to post a comment.
近期评论
- Pika发表在《莫里斯蠕虫(Morris Worm)》
- Pika发表在《多组学科研分析》
- crisy发表在《最近关于专利的一点感想》
- walter发表在《机器学习基础知识回顾-马尔科夫过程(Markov Process)》
文章归档
- 2024年3月
- 2024年2月
- 2023年12月
- 2023年11月
- 2023年10月
- 2023年9月
- 2023年8月
- 2023年7月
- 2023年6月
- 2023年5月
- 2023年4月
- 2023年3月
- 2023年2月
- 2023年1月
- 2022年12月
- 2022年11月
- 2022年9月
- 2022年8月
- 2022年7月
- 2022年6月
- 2022年5月
- 2022年3月
- 2022年2月
- 2022年1月
- 2021年12月
- 2021年11月
- 2021年10月
- 2021年9月
- 2021年8月
- 2021年7月
- 2021年6月
- 2021年5月
- 2021年4月
- 2021年2月
- 2021年1月
- 2020年12月
- 2020年11月
- 2020年10月
- 2020年8月
- 2020年7月
- 2020年6月
- 2020年5月
- 2020年4月
- 2020年3月
- 2020年2月
- 2019年7月
- 2019年5月
- 2019年3月
- 2019年1月
- 2018年6月
- 2018年5月
- 2018年4月
- 2018年3月
- 2018年2月
- 2017年11月
- 2017年7月
- 2017年6月
- 2017年5月
- 2017年3月
- 2016年12月
- 2016年11月
- 2016年10月
- 2016年9月
- 2016年8月
- 2016年7月
- 2016年6月
- 2016年5月
- 2016年4月
- 2016年3月
- 2016年2月
- 2016年1月
- 2015年12月
- 2015年11月