正则表达式匹配

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

#include <stdio.h>

bool matchCore(char* string,char* pattern);

//正则表达式的匹配
bool match(char* str,char* pattern)
{
    if(str == NULL || pattern == NULL)
        return false;

    return matchCore(str,pattern);
}

bool matchCore(char* str,char* pattern)
{
    if(*str == '' && *pattern == '')
        return true;

    if(*str != '' && *pattern == '')
        return false;

    if(*(pattern + 1) == '*') 
    {
        if(*pattern == *str || (*pattern == '.' && *str != ''))
                   // move on the next state
            return matchCore(str + 1,pattern + 2)
                   // stay on the current state 
                || matchCore(str + 1,pattern)
                   // ignore a '*' 
                || matchCore(str,pattern + 2);
        else
                   // ignore a '*'
            return matchCore(str,pattern + 2);
    }

    if(*str == *pattern || (*pattern == '.' && *str != ''))
        return matchCore(str + 1,pattern + 1);

    return false;
}

// ==================== Test Code ====================

void Test(char* testName,char* string,char* pattern,bool expected)
{
    if(testName != NULL)
        printf("%s begins: ",testName);

    if(match(string,pattern) == expected)
        printf("Passed.n");
    else
        printf("FAILED.n");
}

int main(int argc,char* argv[])
{
    Test("Test01","",true);
    Test("Test02",".*",true);
    Test("Test03",".",false);
    Test("Test04","c*",true);
    Test("Test05","a",true);
    Test("Test06","a.",false);
    Test("Test07",false);
    Test("Test08",true);
    Test("Test09","ab*",true);
    Test("Test10","ab*a",false);
    Test("Test11","aa",true);
    Test("Test12","a*",true);
    Test("Test13",true);
    Test("Test14",false);
    Test("Test15","ab",true);
    Test("Test16",true);
    Test("Test17","aaa","aa*",true);
    Test("Test18","aa.a",false);
    Test("Test19","a.a",true);
    Test("Test20",".a",false);
    Test("Test21","a*a",true);
    Test("Test22",false);
    Test("Test23","ab*ac*a",true);
    Test("Test24","ab*a*c*a",true);
    Test("Test25",true);
    Test("Test26","aab","c*a*b",true);
    Test("Test27","aaca",true);
    Test("Test28","aaba",false);
    Test("Test29","bbbba",".*a*a",true);
    Test("Test30","bcbbabab",false);

    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!