面試題：正規表達式比對

題目

請實作一個函數用來比對包含’.’和’‘的正規表達式。模式中的字元’.’表示任意一個字元，而’‘表示它前面的字元可以出現任意次（含0次）。在本題中，比對是指字元串的所有字元比對整個模式。例如，字元串”aaa”與模式”a.a”比對，但與“aa.a”及”ab*a”均不比對。

思路解法：

對單個字元和’.’字元的比對比較簡單，關鍵是’*’怎麼來比對。

‘*’字元的比對情況如下：

‘*’表示它前面的字元可以出現任意次（含0次）

ab*a 可以變成 aa , aba,abba,abbba,…………

以”aaa”和”ab*ac*a”為例

當模式串中第二個字元為”*”時，有下面幾個選擇：

一是在模式上向後移動兩個字元，相當于把’*’和前面的’b’忽略掉了，然後判斷後面的是否比對。

二是如果模式和被比對字元串的第一個字元相同，則被比對字元串向後移動一個字元，模式保持不變。

三是如果模式和被比對字元串的第一個字元相同，則被比對字元串向後移動一個字元，模式向後移動兩個字元。

上面這些情況用遞歸很容易實作。

#include <iostream>    
#include <vector>    
using namespace std;  

bool MatchCore(const char *str, const char *pattern)  
{  
    if (*str == '\0'&&*pattern == '\0') return true;  
    if (*str != '\0'&&*pattern == '\0') return false;  
    if (*(pattern + ) == '*')    
    {  
        if (*str == *pattern || (*pattern == '.'&&*str != '\0')) //有三種情況  
        {  
            return MatchCore(str + , pattern + ) //情況三  
                || MatchCore(str + , pattern)     //情況二  
                || MatchCore(str, pattern + );    //情況一  
        }  
        else                                                     //有一種情況  
            return MatchCore(str, pattern + );  
    }  
    if (*str == *pattern || (*pattern == '.'&&*str != '\0')) //有一種情況  
        return MatchCore(str + , pattern + );  
    return false;  
}  

int main()  
{  
    cout << MatchCore("aaa", "ab*ac*a") << endl;  
    return ;  
}