编写一个正则表达式字符串匹配函数,支持'.','*'和'.*'

Question

标题非常明确,下面是几个样本输入/输出.请注意,所使用的正则表达式应该从字符串的开头到结尾匹配.

'abc' =~ 'abc' (match)
'abc' =~ 'a*bc' (match)
'aaaaaaabc' =~ 'c*bc' (no match)
'aaaaaaabc' =~ 'a.*bc' (match)
'abbbbaaaaaabc' =~ 'ab*a*b*c' (match)
'abbbbaaaaaabc' =~ 'ab*a*h*bc' (match)
'bbd' =~ 'b*bbd' (match)
'bbd' =~ '.*bbd' (match)
'bbd' =~ '.*cbd' (no match)
'' =~ '.*' (match)

我的实现位于:

https://github.com/jpbillaud/piexposed/blob/master/string/string_match_regexp.c

现在我想知道是否有人会考虑使用DP,有限自动机或其他任何方法来解决这个问题.

Answer 1

看看这个实现用正则表达式匹配的罗布·派克,从书中所编程实践.这是绝对漂亮的代码,只需35行C就可以满足问题中的所有要求(还有更多!).引用上面引用的文章:

/* 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;
}