DFA

leetcode 有效数字

leetcode上的一道题目，判断给定的字符串是否是一个有效数字，其中解法用到了编译原理中的DFA(有限状态自动机)，记录一下

题目描述

验证给定的字符串是否可以解释为十进制数字。
题目链接
例如:

"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

这里给的示例不是很全，所以一开时做这道题的时候很多正确的输入都被我判断为错，比如.1e3; 3.e3; 3.e-7; .3e-6;这些都算正确的数字，还有正确的数字后面跟一堆的空白也算正确，比如” 333.33e9 “;

以前解这种题就会使用一堆的if else来各种判断，显然那样写出来的代码不仅臃肿还容易漏掉一些边界条件，所以我们可以使用DFA来解决这个问题：

构建自动机

根据题意构建如下自动机：

图中还有一个状态end没画出来，图中所有的状态如果接受了一个无效的输入都会转到这个end状态，end状态就表明这不是一个合法的数字

然后再用表格表示这个自动机：

state	‘ ‘	+/-	0-9	dot	E	other
start	start	sign	in_num	pre_decimal	end	end
sign	end	end	in_num	pre_decimal	end	end
in_num	end_space	end	in_num	decimal	pre_exponent	end
decimal	end_space	end	decimal	end	pre_exponent	end
exponent	end_space	end	exponent	end	end	end
pre_decimal	end	end	decimal	end	end	end
pre_exponent	end	pre_sign	exponent	end	end	end
pre_sign	end	end	exponent	end	end	end
end_space	end_space	end	end	end	end	end
end	end	end	end	end	end	end

代码

有了自动机的表格，我们就可以对照着表格来写出对应的代码：

class Automaton{
    string state = "start";
    map<string,vector<string>> table = {
        {"start",{"start","sign","in_num","pre_decimal","end","end"}},
        {"sign",{"end","end","in_num","pre_decimal","end","end"}},
        {"in_num",{"end_space","end","in_num","decimal","pre_exponent","end"}},
        {"decimal",{"end_space","end","decimal","end","pre_exponent","end"}},
        {"exponent",{"end_space","end","exponent","end","end","end"}},
        {"pre_decimal",{"end","end","decimal","end","end","end"}},
        {"pre_exponent",{"end","pre_sign","exponent","end","end","end"}},
        {"pre_sign",{"end","end","exponent","end","end","end"}},
        {"end_space",{"end_space","end","end","end","end","end"}},
        {"end",{"end","end","end","end","end","end"}}
    };

    int get_col(char c){
        if(isspace(c)) return 0;
        if(c == '+' || c == '-') return 1;
        if(isdigit(c))  return 2;
        if(c == '.') return 3;
        if(c == 'e') return 4;
        return 5;
    }

public:
    bool check(string& s){
        int len = s.size();
        for(int i = 0;i < len;i++){
            state = table[state][get_col(s[i])];
            if(state == "end"){
                return false;
            }
        }
        // 不是这四个状态之一就不是合法的数字
        if(state != "end_space" && state != "exponent" && state != "in_num" && state != "decimal")
            return false;
        
        return true;
    }

};

class Solution {
public:
    bool isNumber(string s) {
        Automaton automaton;
        return automaton.check(s);
    }
};

可以看到使用DFA来解决这种问题，代码逻辑就会很清晰，也不会怕漏掉什么边界条件，但是前提状态图要画对 :P，当然这里也可以把状态的名字直接用数字来表示，这样更节省内存，也会更快一些

总的来说，比我以前傻傻的用一堆的if else判断来的好太多了