《代码之美》-- 正则表达式

在《代码之美》一书中,作者展示了一段大约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;
}