[C++] My thought with DFA


  • 44
    Y

    Code first

    class Solution {
    public:
        bool isNumber(string str) {
            int state=0, flag=0; // flag to judge the special case "."
            while(str[0]==' ')  str.erase(0,1);//delete the  prefix whitespace 
            while(str[str.length()-1]==' ') str.erase(str.length()-1, 1);//delete the suffix whitespace
            for(int i=0; i<str.length(); i++){
                if('0'<=str[i] && str[i]<='9'){
                    flag=1;
                    if(state<=2) state=2;
                    else state=(state<=5)?5:7;
                }
                else if('+'==str[i] || '-'==str[i]){
                    if(state==0 || state==3) state++;
                    else return false;
                }
                else if('.'==str[i]){
                    if(state<=2) state=6;
                    else return false;
                }
                else if('e'==str[i]){
                    if(flag&&(state==2 || state==6 || state==7)) state=3;
                    else return false;
                }
                else return false;
            }
            return (state==2 || state==5 || (flag&&state==6) || state==7);
        }
    };
    

    DFA

    Thank @unknowcs, he came up with a brilliant provement in comments that making this a perfect DFA!

    It's just some states changes depend on inputs only.

    There 8 state in my states in my DFA.
    Below is my DFA transition diagram.

    DFA transition diagram

    or click picture here
    DFA transition diagram

    There are 5 kind of inputs in my DFA:

    digit : number 0-9 for

    +,- : operator + or -(negative or positive)

    exp: e

    dot: .

    other: you can return false Immediately

    4 final States in my DFA transition diagram : s2, s6, s7, s8

    If the state change to final state at last, return true.

    s2 can accept digits only : +1 -23432 123 and etc

    s5 can accept exp expression: +2.4e+12 3e9 and etc

    s6 can accept decimals end with dot: 1. -42. and etc
    (careful, what if there exist only one dot "."
    **** I use a variable flag judging weather there existing numbers. cause 0. and .0 is valid and . is invalid ****
    )

    s7 can accept decimals: +12.23, 87., 132

    It is clear how DFA works in my pictures. We just need to handle the inputs, and update the state according to DFA.


  • 0
    R

    Nice Solution! It helps me, thanks.


  • 0
    R

    The dfa can not be accepted by the OJ, as '.' is invalid....but '.1' is valid. I have implemented your dfa but it failed on '.' case which OJ expect false


  • 0
    Y

    that's why I use a variable judging whether numbers behind dot
    我用了一个变量flag来判断,小数点后面有没有数字


  • 0
    R

    but "3." is valid, "." is invalid, so maybe you can not judge them by whether there exists digit behind dot. And also dfs accept ".e123", which was invalid by the judge. How to solve it


  • 0
    Y

    my mistake.

    the variable "flag" is judging weather there existing number.

    nothing to do with the dot position so that can handle weather 3. or .3


  • 0
    R

    And also you should add a logic condition, that is if no digit appear when met e, it would invalid directly. And also final state of S6 should have digits. Adding these two issue, the DFA will be accepted, thus would not misleading other coders : ) I wonder whether there exists a single DFA that can be accepted by OJ without adding flag variable ?


  • 0
    Y

    Thanks! And e5 is a valid number, actually. I should update my post.


  • 0
    R

    e5 is invalid, because no digits before e.


  • 0
    Y

    sorry, it was too long ago for me to recall details. Now I take a look at my code and my image. It is true that e5 is invalid and there is no way match e5 cause it'll return false when 'e' occur in 'e5' case


  • 0
    B

    thx for your diagram. What do you mean by (flag&&state==6)? in your diagram flag 6 is not a final state. Is "1." a valid input? what about "1.e2"?


  • 0
    Y

    nice question. The variable flag determine weather number existing, cause single dot '.' is not acceptable. '1.' and '.1' are valid. 1.e2 will go to s5, which means valid too


  • 0
    U

    I think there is something wrong in your DFA diagram. According you diagram, '.' is a valid number whereas it's invalid.


  • 0
    Y

    Nice observation! Thus I use variable 'flag' judging whether there existing number. It was mentioned above.


  • 0
    U

    Got it! How about not setting S6 as a final states? It will spare the usage of flag.


  • 0
    Y

    cause '1.' is also a valid number.


  • 0
    R

    whether exist a complete correct DFA for this problem? I mean without flag?


  • 0
    U

    You can modify the arrow that points from S2 to S6 as pointing from S2 to S7. And at the same time, set S6 as a non-final state.


  • 0
    Y

    Brilliant! I should mention you idea in pragraph.


  • 0
    R

    I think another modify need: delete point from S6 to S3, as .e3 is invalid, before e, if . exist, digit is needed (before or after dot). Why input here so slow........ here is modified DFA http://postimg.org/image/q7xvr1wxv/ and my code has ACed according to this DFA http://paste.ubuntu.com/9496785/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.