正则表达式匹配

编辑于 2017-01-28

* 移动设备下, 可左滑手指以查看较宽代码

问题

实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配。

分析

思路:只有当模式串和字符串同时等于\0,才可以认为两个串匹配。 在匹配中,对于每个位的匹配可以分为三种情况:

1)(相应位匹配 || 模式串为. && 字符串不是\0) && 模式串下一位是*:分匹配0次和匹配>0次两种情况,符合一种情况即匹配

*取0对应跳过当前匹配位,继续寻找 pattern 的下一个匹配位,str 不变,pattern+2。

*取>0对应一次成功匹配,继续匹配字符串的下一位是否匹配,str+1,pattern不变。

2)(相应位匹配 || 模式串为. && 字符串不是\0) && 模式串下一位不是*:相当于一次成功匹配,str+1,pattern+1

3)相应位不匹配 && (模式位不为. || 字符串是\0) :匹配失败,直接返回false

代码

bool matchCore(char* str, char* pattern)
{
    if(*str=='\0'&&*pattern=='\0')
        return true;
    if(*str!='\0'&&*pattern=='\0')
        return false;
    if(*(pattern+1)=='*'){
        if(*pattern==*str||(*pattern=='.'&&*str!='\0'))
            return matchCore(str+1,pattern)||matchCore(str,pattern+2);
        else
            return matchCore(str,pattern+2);
    }
    if(*str==*pattern||(*pattern=='.'&&*str!='\0'))
        return matchCore(str+1,pattern+1);
    return false;
}
bool match(char* str, char* pattern)
{
    if(str==NULL || pattern==NULL)
        return false;
    return matchCore(str,pattern);
}