Friday, October 11, 2013

Valid Number

Borrow the solution from here: Use DFA to solve the problem.
http://discuss.leetcode.com/questions/241/valid-number

class Solution {
public:
    enum token {
        space,
        digit,
        sign,
        dot,
        exp,
        invalid
    };
    
    bool isNumber(const char *s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int table[][6] = {
            {0, 1, 2, 3, -1, -1},
            {8, 1, -1, 4, 5, -1}, 
            {-1, 1, -1, 3, -1, -1}, 
            {-1, 4, -1, -1, -1, -1},
            {8, 4, -1, -1, 5, -1},
            {-1, 7, 6, -1, -1, -1},
            {-1, 7, -1, -1, -1, -1},
            {8, 7, -1, -1, -1, -1},
            {8, -1, -1, -1, -1, -1}
        };
        token curr_token;
        int curr_state = 0;
        while (*s != '\0') {
            curr_token = invalid;
            if (isdigit (*s))
                curr_token = digit;
            if (isspace (*s))
                curr_token = space;
            if (*s=='+' || *s=='-')
                curr_token = sign;
            if (*s == '.')
                curr_token = dot;
            if (*s=='e' || *s=='E')
                curr_token = exp;
            curr_state = table[curr_state][curr_token];
            if (curr_state == -1)
                return false;
            s++;
        }
        return (curr_state==1 || curr_state==4 || curr_state==7 || curr_state==8);
    }
};

No comments:

Post a Comment