DFA

https://leetcode.com/problems/valid-number/

使用if-else实现DFA

class Solution {
public:
    bool isNumber(string s) {
        while(!s.empty() && s[0] == ' ') {
            s.erase(s.begin());
        }
        while (!s.empty() && s[s.size() - 1] == ' ') {
            s.erase(s.end() - 1);
        }
        if(s.empty()) return false;
        int state = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '-' || s[i] == '+') {
                if(state == 0 || state == 3) {
                    state ++;
                } else return false;
            } else if(s[i] == '.') {
                if( state == 2) {
                    state = 7;
                } else if(state == 0 || state == 1) {
                    state = 6;
                } else return false;
            } else if(s[i] >= '0' && s[i] <= '9') {
                if(state == 1 || state == 4 || state == 6) {
                    state ++;
                } else if(state == 0 || state == 3) {
                    state = state + 2;
                }
            } else if(s[i] == 'e' || s[i] == 'E') {
                if(state == 2 ||  state == 7) {
                    state = 3;
                } else return false;
            } else return false;
        }
        return state == 2 || state == 7 || state == 5;
    }
};

使用状态转换表实现DFA

状态表行代表状态数量，列代表输入类型

class Solution {
public:
    int CharIndex(char c) {
        if(c == '+' || c == '-' ) return 0;
        else if(isdigit(c)) return 1;
        else if(c == '.') return 2;
        else if(c == 'e' || c == 'E') return 3;
        else
            return -1;
    }
    bool isNumber(string s) {
        //+,-  digit  dot  exp
        int transfer[8][4] = {
            1, 2, 6, 0,
            0, 2, 6, 0,
            0, 2, 7, 3,
            4, 5, 0, 0,
            0, 5, 0, 0,
            0, 5, 0, 0,
            0, 7, 0, 0,
            0, 7, 0, 3
        };
        // delete preceding space
        while(!s.empty() && s[0] == ' ') {
            s.erase(s.begin());
        }
        while(!s.empty() && s[s.size() - 1] == ' ') {
            s.erase(s.end() - 1);
        }
        // only with space
        if(s.empty()) return false;
        int status = 0;
        for(int ii = 0; ii < s.size(); ii++) {
            int i = CharIndex(s[ii]);
            if(i == -1) return false;
            status = transfer[status][i];
            if(!status) return false;
        }
        return status == 2 || status == 5 || status == 7;
    }
};

状态转化图