字符串正则表达式

半成品（说垃圾太打击自己了）：

#include <iostream>
#include <algorithm>

using namespace std;
//牛客网，字符串匹配题目。

 string& ReverseIt(string &originalPattern, string &originalSon);   //字符串反转；
int main()
{
    //test pattern;
    string patern1 = "qadffgfgr.";
    string patern2 = "a.s.d.f...g....hjk....l";
    string pattern3 = "a*sdf*g*hjkl";

    string son= "fgh";

    int CharHaveBeenMatched = 0;
    //version1；
    int LengthOfSon = son.length();
    int LengthOfPattern = patern1.length();
    int PtArrNum = 0;
    int SonArrNum = 0;
    int ShowTime = 1;
    while (true)
    {
        if(CharHaveBeenMatched < LengthOfSon)
        {
            if((LengthOfSon-SonArrNum) > (LengthOfPattern-PtArrNum)){
                cout<<" stop"<<endl;
                break;
            }
            if(patern1[PtArrNum] == '.'){
                ++CharHaveBeenMatched;
                ++PtArrNum;
                ++SonArrNum;
                continue;
            }
            if(patern1[PtArrNum] == '*')
            {
                if(son[SonArrNum] == patern1[PtArrNum+1])
                {
                    //判断子串是否连续相同；
                    for(int i=1; patern1[PtArrNum] == patern1[PtArrNum+i]; ++i){
                        ++ShowTime;
                    }
                    if(ShowTime > 1){
                        SonArrNum +=(ShowTime+1);
                        patern1 += 1;
                        CharHaveBeenMatched += ShowTime;
                        continue;
                    }else {
                        ++ShowTime;
                        ++PtArrNum;
                        ++SonArrNum;
                        continue;
                    }
                }else {//不相等，父串进2，子串不变；
                    PtArrNum += 2;
                    continue;
                }
            }
            //父串中为正常的字符；（约束在小写字符之内）
            if(patern1[PtArrNum] < 'z' && patern1[PtArrNum] > 'a'){
                if(son[SonArrNum] == patern1[PtArrNum]){
                    ++CharHaveBeenMatched;
                    ++PtArrNum;
                    ++SonArrNum;
                    continue;
                }else {
                    ++PtArrNum;
                    continue;
                }
            }
        }
        else if(CharHaveBeenMatched == LengthOfSon){
            cout<<" match success!!!"<<endl;
            break;
        }
        else {
            cout<<"failed!!!"<<endl;
        }
    }
    return 0;
}

string& ReverseIt(string &originalPattern, string &originalSon)
{
    reverse(originalPattern.begin(), originalPattern.end());
    reverse(originalSon.begin(), originalSon.end());
}

           

思路如下：

失败。

先不说解题思路，代码风格。说几个原则上的失败：

①胆小怕事。懒得写，懒得改。磨磨蹭蹭拖了3个晚上，第一个晚上看别人的代码睡着了；第二个晚上画流程图睡着了。第三个晚上（现在）磨出来个废品。就应当想到那里流程图画到哪里，哪怕是搞出来个垃圾，还有有时间、有思路去学习别人的套路。

②过度依赖网上的成品。可行的不一定就是好的。有些案例，拿着c++，用C语言的思想，路子从头写。甚至部分内容就是对库函数的实现。这不好。

收获：了解了string丰富的用法。知道迭代器的具体用法。

————————————————————————————

开心，把屎山解决了。

#include <iostream>

using namespace std;

bool matchcore(char *str, char * pattern)
{
    if('\0' == *str && '\0' == *pattern)  return true;    //这一题的大坑—pattern串的长度
//    if('\0' == *str && '\0' != *pattern)    return true;  //个人添加——这是不符合题意的，会造成模式不符合；
    if('\0' != *str && '\0' == *pattern)  return false;

    //始终不能解释a*a如何与aaa匹配——不用解释，二者模式补符合；
    if('*' == *(pattern+1))
    {
        if(*str == *pattern || ('.' == *pattern && '\0' != *str))
            return matchcore(str+1, pattern) || matchcore(str, pattern+2);  //两个并行的分支；
        else
            return matchcore(str, pattern+2);
    }

    if(('.' == *pattern && '\0' != *str) || (*pattern == *str))
        return matchcore(str+1, pattern+1);    //比一对字符，扔一对字符；

    return false;
}

bool matchstr(char *str, char * pattern)
{
    //空字符串，报错；
    if(NULL == str && NULL == pattern){
        return false;
    }

    return  matchcore(str, pattern);
}

int main()
{
    char * str = "aaa";
//    char * pattern = "a*a*a";
    char *pattern = ".*aaaaa";

    bool result = matchstr(str, pattern);
    cout<<result<<endl;
    return 0;
}
           

最关键的一点：题意。

之前考虑的情况偏离了题意，这里强调模式相同即a*a与aaa也是不匹配的，“ * ”号之前的a不能匹配整个aaa串。出现这种情况时，应当进入下面的循环。

出现上述情况的最极端例子：“ .*a ”,此时对应的举措就是将“ . * ”视为出现0次。另一种更为普遍的例子（如上文），则进入普通循环，直到出现

if（‘\0’ == str && ‘\0’ != pattern），return false；

值得借鉴的思想：这里采用递归的方式解决问题，这种方式代码简洁，但是若字符串过长，复杂度大大增加，有爆栈风险。