自动机系列之一：自动机的模板代码及其demo

快来打我* 2022-06-07 05:49 178阅读 0赞

里面一个函数就是一个自动机，其中包括了正则的自动机，是否为数字的的自动机等

#include <iostream>
    
    using namespace std;
    
    bool isNumber(string s)
    {
        enum InputType
        {
            INVALID,    // 1. invalid input
            SIGN,       // 2. '+' or '-'
            DIGIT,      // 3. digits
            DOT,        // 4. '.'
            EXP         // 5. 'e'
        };
        const int NUM_INPUT = 5;
        if(s == " ") return false;
        //get rid of space
        int start = s.find_first_not_of(" ");
        int end = s.find_last_not_of(" ");
        string ss = s.substr(start, end-start+1);
        int n = ss.size();
    
        int state = 0;
        const int transitionTable[][NUM_INPUT] =
        {
           -1, 3, 1, 2, -1,
           -1, -1, 1, 4, 5,
           -1, -1, 4, -1, -1,
           -1, -1, 1, 2, -1,
           -1, -1, 4, -1, 5,
           -1, 6, 7, -1, -1,
           -1, -1, 7, -1, -1,
           -1, -1, 7, -1, -1,
           -1, -1, 7, -1, -1,
        };
    
        for(int i = 0; i < n; ++i)
        {
            InputType type = INVALID;
            if(ss[i] == '+' || ss[i] == '-')
            {
                type = SIGN;
            }
            else if(isdigit(ss[i]))
            {
                type = DIGIT;
            }
            else if(ss[i] == '.')
            {
                type = DOT;
            }
            else if(ss[i] == 'e' || ss[i] == 'E')
            {
                type = EXP;
            }
            state = transitionTable[state][type];
    
            if(state == -1) return false;
        }
        return state == 1 || state == 4 || state == 7;
    }
    
    bool isABAB(string s)
    {
        enum InputType
        {
            A,    // input a
            B,       // input b
            OTHER    //other input
        };
        const int NUM_INPUT = 3;
        if(s == " ") return false;
        //get rid of space
        int start = s.find_first_not_of(" ");
        int end = s.find_last_not_of(" ");
        string ss = s.substr(start, end-start+1);
        int n = ss.size();
    
        int state = 0;
        const int transitionTable[][NUM_INPUT] =
        {
           0, 1, -1,            //技巧就是从0状态开始建可能效果更好
           -1, 0, -1,
        };
    
        for(int i = 0; i < n; ++i)
        {
            InputType type = OTHER;
            if(ss[i] == 'a')
            {
                type = A;
            }
            else if(ss[i]=='b')
            {
                type =  B;
            }
            else{
                type = OTHER;
            }
            state = transitionTable[state][type];
    
            if(state == -1) return false;
        }
        return state == 0  ;
    }
    
    bool isABBA(string s)
    {
        enum InputType
        {
            A,    // input a
            B,       // input b
            OTHER    //other input
        };
        const int NUM_INPUT = 3;
        if(s == " ") return false;
        //get rid of space
        int start = s.find_first_not_of(" ");
        int end = s.find_last_not_of(" ");
        string ss = s.substr(start, end-start+1);
        int n = ss.size();
    
        int state = 1;
        const int transitionTable[][NUM_INPUT] =
        {
           -1, -1, -1,      //error state
           1 , 2 , -1,
           3 , 2 , -1,
           3 , -1, -1
        };
    
        for(int i = 0; i < n; ++i)
        {
            InputType type = OTHER;
            if(ss[i] == 'a')
            {
                type = A;
            }
            else if(ss[i]=='b')
            {
                type =  B;
            }
            else{
                type = OTHER;
            }
            state = transitionTable[state][type];
    
            if(state == -1) return false;
        }
        return state == 3  ||state==2;
    }
    
    bool isIpv4Add(string s)
    {
        enum InputType
        {
            NUM,    // input umber
            DIGIT,       // input igit
            OTHER    //other input
        };
        const int NUM_INPUT = 3;
        if(s == " ") return false;
        //get rid of space
        int start = s.find_first_not_of(" ");
        int end = s.find_last_not_of(" ");
        string ss = s.substr(start, end-start+1);
        int n = ss.size();
    
        int state = 1;
        const int transitionTable[][NUM_INPUT] =
        {
            // d . other
    /*0*/ 0, 0, 0,//Error state
    /*1*/ 2, 0, 0,
          3, 5, 0,
          4, 5, 0,
          0, 5, 0,
    /*5*/ 6, 0, 0,
          7, 9, 0,
          8, 9, 0,
          0, 9, 0,
    /*9*/ 10,0, 0,
          11,13,0,
          12,13,0,
          0, 13,0,
    /*13*/ 14,0, 0,
          15,0, 0,//final state
          16,0, 0,//final state
          0, 0, 0 //final state
        };
    
        for(int i = 0; i < n; ++i)
        {
            InputType type = OTHER;
            if((ss[i]-'0')>=0 && (ss[i]-'0')<=9)
            {
                type = NUM;
            }
            else if(ss[i]=='.')
            {
                type =  DIGIT;
            }
            else{
                type = OTHER;
            }
            state = transitionTable[state][type];
    
            if(state == 0) return false;
        }
        return state == 14 || state==15 || state==16  ;
    }
    
    
    int main()
    {
        string s;
        for(int i=0;i<10;i++){
            cin>>s;
            cout << "Hello world!" << endl;
            if(isABBA(s)){
                cout<<"yes"<<endl;
            }
            else{
                cout<<"no"<<endl;
            }
        }
        return 0;
    }