[leetcode] Valid Number — 用有限状态自动机解题 1


Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

输入一个字符串,判断它是不是有效的数字。

从例子中可以看出,该数字可以是整数,小数,甚至是科学计数法表示的数字(2e10);字符串的开头和结尾可以是空白符。并且开头可以有符号(+/-)。

2e10表示2的10次方,在AeB形式的数字中,A为一个正(负)数,B为一个正(负)整数

编译原理课和计算原理课上,我们曾学过有限状态自动机。其中的一种表示方法为DFA(Deterministic Finite Automata),确定有限状态自动机。

其中正则表达式(Regular expression)等价于非确定有限状态自动机(NFA),等价于确定有限状态自动机(DFA)。

也即RE<==>NFA<==>DFA

并且我们有程序化的算法可以把RE转化为NFA再转化为DFA。然后借助DFA进行编程就非常容易了。(扯远了)

Untitled

图1: Sildes of Compiling Techniques, the University of Hong Kong

对于此题,我们先从正则表达式入手,符合题目要求的字符串用一个正则表达式表示。然后将正则表达式转换为DFA,再进行编程。思路会比较清晰。

编程时我们考虑,每读入一个新字符,我们就在DFA中进行一次状态转移。

我们先从最简单的整数入手,并且假设输入中不含有空白符。

1. 整数的正则表达式和DFA

整数的开头可能带符号,并且有多个数字出现,0可以位于开头。(比如00032是合法的)

所以整数的正则表达式为:

(-|\+)?\d+             (1)

其中\d表示一个0-9的数字;(-|\+)?表示数字的开头可以有符号,或者没有。

注意这里是\d+而不是\d*。因为我们认为单有一个符号或是空字符串不是合法的。

把(1)式转化为DFA即为:

webwxgetmsgimg-(1)

DFA中共有1,2,3三个状态。1为起始状态,3为结束状态(同心环)。

n表示输入时一个0-9的数字,即正则中的\d符号。(抱歉我画图时脑袋里想的是number的首字母)

如果输入字符串停在状态3,则该字符串是合法的(一个整数)。

如果输入字符串没有停在状态3,则该字符串是非法的。

如果输入字符串出现了未在DFA中表示的字符,则跳到错误状态,表示该字符串不合法(比如突然出现一个字母或是奇奇怪怪的符号)。

2.整数或小数的正则表达式和DFA

我们在1的基础上,把小数也添加到正则表达式中。

需要指出,”.3″或”3.”都是合法的小数(分别表示0.3和3.0),但单独一个”.”符号则是非法的。(可以在Python中试一下)

包含整数和小数的正则表达式为:

(-|\+)?(\d+\.?\d*|\.\d+)                (2)

上面的正则表达式很复杂,容易看晕。实际解题时,我们可以直接画DFA的,这样会更加直观。

把(2)式转化为DFA:

webwxgetmsgimg

上图共有五个状态,如果输入停在了状态3,则是一个整数;如果停在了状态5,则是一个小数。

如果停在了其他状态,或是出现了一个DFA中没有标明的输入,则非法。

3.整数、小数或科学计数法的正则表达式和DFA

最后,我们把科学计数法表示的数也加入到我们的正则中。

还记得本文开头提到的,科学计数法表示的数可以写为AeB的形式,其中A为正(负)数,B为正(负)整数吗?

(2)式已经把A给表示出来了,我们需要在(2)式后面再添加上eB的形式。

注意,前方高能。。。

高能。。

能。

 

(-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)?                           (3)

 

我们不管它 ,还是来看DFA吧:

webwxgetmsgimg-(2)

(上图应为小数、整数、科学计数法的DFA,请忽略标题……)

图中共有8个状态,前五个状态与(2)中的DFA完全一致,新加入的6,7,8是对应AeB中的B部分。实际上,B是一个正整数,所以你会发现678状态和123状态惊人地相似。

如果停在状态8,则输入是一个科学计数法表示的数字。

4. 开始编程

好了,我们可以根据上图画出的完整DFA进行编程了。

且慢,我们忽视了字符串开头和结尾存在空白字符的情况,如果加入空白字符的情况的话,DFA中需要增加一个状态来处理结尾的空白符,然后在正则表达式的首尾增加\s*匹配空白符:

\s*(-|\+)?(\d+\.?\d*|\.\d+)(e(-|\+)?\d+)?\s*                           (4)

请忽视上面的正则,因为在编程中并不会用到。

表示有限状态自动机的方法有很多,可以用一个二维数组,数组中存储的是相应的输入所应该跳转到的状态位置。或者是用函数表示法,每个状态用一个函数表示,状态的转移用函数的调用表示。

比如该作者的解法,就是用了一个二维数组transitionTable来记录DFA。

链接:https://github.com/fuwutu/LeetCode/blob/master/Valid%20Number.cpp

我们则采用函数表示法,会更直观一些。

我们用函数state1-state9表示DFA中的状态1-状态9.其中状态9是为了处理末尾的空白符。(开头的空白符可以通过修改状态1,在状态1中处理掉)

函数的返回值为bool。true表示字符串合法,false表示非法。

函数的参数为一个string,表示程序运行到该状态时输入的字符串。这里我们传了string的引用来节省内存开销。

    bool isNumber(string s) {
        return state1(s);
    }

首先主调函数调用state1,我们进入起始状态。

bool state1(string& s){
        //parse whitespace 
        while(s.empty() == false && s[0] == ' '){
            s.erase(s.begin());
        }
        //i'm not an end state
        if(s.empty() == true){
            return false;
        }
        //go to state 2
        if(s[0] == '-' || s[0] == '+'){
            s.erase(s.begin());
            return state2(s);
        }
        //go to state 3
        else if(isNumeric(s[0])){
            s.erase(s.begin());
            return state3(s);
        }
        //go to state 4
        else if(s[0] == '.'){
            s.erase(s.begin());
            return state4(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }

state1不是终结状态,如果s.empty(),返回false;

否则,取出s的第一个字符c。根据DFA,如果c == ‘-‘ || c == ‘+’ 跳至state2

如果c==’.’ ,跳至state4;

如果c是一个数字,跳至state3;

否则,输入不合法,返回false;

其他状态与此类似,每个状态函数的结构都很相似。

C++代码如下,它很长,但每个函数的结构都很简单,只要把每个函数与DFA中的相应状态关联起来就好。

class Solution {
public:
    bool isNumber(string s) {
        return state1(s);
    }
    bool state1(string& s){
        //parse whitespace 
        while(s.empty() == false && s[0] == ' '){
            s.erase(s.begin());
        }
        //i'm not an end state
        if(s.empty() == true){
            return false;
        }
        //go to state 2
        if(s[0] == '-' || s[0] == '+'){
            s.erase(s.begin());
            return state2(s);
        }
        //go to state 3
        else if(isNumeric(s[0])){
            s.erase(s.begin());
            return state3(s);
        }
        //go to state 4
        else if(s[0] == '.'){
            s.erase(s.begin());
            return state4(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state2(string &s){
        //this is not the end state
        if(s.empty()){
            return false;
        }
        //go to state 3
        if(isNumeric(s[0])){
            s.erase(s.begin());
            return state3(s);
        }
        //go to state 4
        else if(s[0] == '.'){
            s.erase(s.begin());
            return state4(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state3(string &s){
        //parse numbers
        while(s.empty() == false && isNumeric(s[0])){
            s.erase(s.begin());
        }
        //i'm an end state, got an integer
        if(s.empty()){
            return true;
        }
        //go to state 6, may be an exponent
        if(s[0] == 'e'){
            s.erase(s.begin());
            return state6(s);
        }
        //go to state 5, may be a float
        else if(s[0] == '.'){
            s.erase(s.begin());
            return state5(s);
        }
        //go to state 9, parse whitespaces at tail
        else if(s[0] == ' '){
            s.erase(s.begin());
            return state9(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state5(string &s){
        //parse number
        while(s.empty() == false && isNumeric(s[0])){
            s.erase(s.begin());
        }
        //i'm an end state
        if(s.empty()){
            return true;
        }
        //go to state 9, parse whitespace at tail
        if(s[0] == ' '){
            s.erase(s.begin());
            return state9(s);
        }
        //go to state 6
        else if(s[0] == 'e'){
            s.erase(s.begin());
            return state6(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state4(string &s){
        //i'm not an end state
        if(s.empty()){
            return false;
        }
        //go to state 5
        if(isNumeric(s[0])){
            s.erase(s.begin());
            return state5(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    
    bool state6(string &s){
        //i'm not an end state
        if(s.empty()){
            return false;
        }
        //go to state 7
        if(s[0] == '-' || s[0] == '+'){
            s.erase(s.begin());
            return state7(s);
        }
        //go to state 8
        else if(isNumeric(s[0])){
            s.erase(s.begin());
            return state8(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state7(string &s){
        //i'm not an end state
        if(s.empty()){
            return false;
        }
        //go to state 8
        if(isNumeric(s[0])){
            s.erase(s.begin());
            return state8(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state8(string &s){
        //parse number
        while(s.empty() == false && isNumeric(s[0])){
            s.erase(s.begin());
        }
        //i'm an end state
        if(s.empty()){
            return true;
        }
        if(s[0] == ' '){
            s.erase(s.begin());
            return state9(s);
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool state9(string &s){
        //parse whitespace
        while(s.empty() == false && s[0] == ' '){
            s.erase(s.begin());
        }
        //i'm an end state
        if(s.empty()){
            return true;
        }
        //not an acceptable char
        else{
            return false;
        }
    }
    bool isNumeric(char c){
        return c <= '9' && c >= '0';
    }
};

时间复杂度o(n),n为字符串长度。

因为DFA中没有环路出现。所以最大的调用深度即为最长的到结束状态的路径,为1->2->4->5->6->7->8,7层。

速度还是比较理想的。

Selection_037

 

2015.4.11

于浙大玉泉


Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

One thought on “[leetcode] Valid Number — 用有限状态自动机解题