在《代码之美》一书中,作者展示了一段大约30行的C代码,实现了一个正则表达式匹配器。
该正则表达式提供了如下匹配模型:
字符 | 含义 |
---|---|
c | 匹配任意字母c |
. | 匹配任意单个字符 |
^ | 匹配输入字符串的开头 |
$ | 匹配输入字符串的结尾 |
. | 匹配前一个字符的零个或多个出现 |
这是非常有用的匹配器,基本上可以解决95%左右的正则匹配问题。这段代码写的紧凑 、优雅、高效并且实用。这段代码充分展示了c指针的强大功能,以及递归的极佳示例。
你可以自己动手实现一下上面的功能,然后再来对比一下书中这段代码,看看是否也能实现的如此精简高效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* match: search for regexp anywhere in text */
int match(char *regexp, char *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;
}
/* matchhere: search for regexp at beginning of text */
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: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
do { /* a * matches zero or more instances */
if (matchhere(regexp, text))
return 1;
} while (*text != '\0' && (*text++ == c || c == '.'));
return 0;
}