Solution in C [ runtime 3ms ]


  • 1
    A

    {{{
    enum { S_START, // beginning of expression
    S_INT, // When at least one Int has been read
    S_SIGNED, // A plus sign has been read
    S_INT_EXP, // Integer and Exponential
    S_INT_E, // Intermediate state with Int followed by a e sign
    S_DOT,
    S_SDOT,// Dot symbol has been read
    S_FLOAT_A, // Intermediate state
    S_FLOAT,
    S_NUM_SP,
    S_ACCEPTED,
    S_INVALID,
    NUM_STATES };
    enum { A_CONT, A_ACCEPT, A_REJECT };
    enum { IN_INT, IN_MINUS, IN_PLUS, IN_SPACE, IN_DOT, IN_NULL, IN_EXP, IN_OTHER, NUM_TYPES };

    struct fsm_action {
    int state;
    int action;
    };

    struct fsm_action table [NUM_STATES][NUM_TYPES];

    void fsm_fill (void) {

    table [S_START][IN_INT]   = (struct fsm_action){ S_INT, A_CONT };
    table [S_START][IN_OTHER] = (struct fsm_action){ S_INVALID, A_REJECT };
    table [S_START][IN_DOT]   = (struct fsm_action){ S_SDOT, A_CONT};
    table [S_SDOT][IN_INT]   =  (struct fsm_action){ S_FLOAT, A_CONT};
    table [S_START][IN_SPACE] = (struct fsm_action){ S_START, A_CONT};
    table [S_START][IN_MINUS] = (struct fsm_action){ S_SIGNED, A_CONT};
    table [S_START][IN_PLUS] = (struct fsm_action){ S_SIGNED, A_CONT };
    
    table [S_SIGNED][IN_INT] = (struct fsm_action){ S_INT, A_CONT};
    table [S_SIGNED][IN_DOT] = (struct fsm_action){ S_SDOT, A_CONT};
    
    table [S_DOT][IN_INT]     = (struct fsm_action){ S_FLOAT_A, A_CONT };
    table [S_DOT][IN_NULL]    = (struct fsm_action){ S_INVALID, A_REJECT};
    
    table [S_INT][IN_SPACE]   = (struct fsm_action){ S_NUM_SP, A_CONT };
    
    table [S_INT][IN_INT]     = (struct fsm_action){ S_INT, A_CONT };
    table [S_INT][IN_DOT]     = (struct fsm_action){ S_FLOAT_A, A_CONT };
    table [S_INT][IN_NULL]    = (struct fsm_action){ S_ACCEPTED, A_ACCEPT };
    table [S_INT][IN_OTHER]   = (struct fsm_action){ S_INVALID, A_REJECT };
    table [S_INT][IN_EXP]     = (struct fsm_action){ S_INT_E, A_CONT };
    table [S_INT_E][IN_PLUS]  = (struct fsm_action){ S_INT_E, A_CONT};
    table [S_INT_E][IN_MINUS]  = (struct fsm_action){ S_INT_E, A_CONT};
    table [S_FLOAT_A][IN_EXP] = (struct fsm_action){ S_INT_E, A_CONT};
    
    
    table [S_SIGNED][IN_SPACE]  = (struct fsm_action){ S_NUM_SP, A_CONT};
    
    
    table [S_NUM_SP][IN_SPACE]  = (struct fsm_action){ S_NUM_SP, A_CONT};
    table [S_NUM_SP][IN_NULL]  = (struct fsm_action){ S_ACCEPTED, A_ACCEPT};
    
    
    
    
    
    
    table [S_INT_E][IN_INT]   = (struct fsm_action){ S_INT_EXP, A_CONT };
    table [S_INT_EXP][IN_INT] = (struct fsm_action){ S_INT_EXP, A_CONT };
    table [S_INT_EXP][IN_NULL] = (struct fsm_action){ S_ACCEPTED, A_ACCEPT};
    table [S_INT_EXP][IN_SPACE] = (struct fsm_action){ S_NUM_SP, A_CONT };
    
    
    
    table [S_FLOAT_A][IN_INT] = (struct fsm_action){ S_FLOAT, A_CONT };
    table [S_FLOAT_A][IN_SPACE] = (struct fsm_action){ S_NUM_SP, A_CONT };
    table [S_FLOAT][IN_EXP] = (struct fsm_action){ S_INT_E, A_CONT};
    table [S_FLOAT][IN_SPACE] = (struct fsm_action){ S_NUM_SP, A_CONT };
    
    
    table [S_FLOAT_A][IN_NULL] = (struct fsm_action){ S_ACCEPTED, A_ACCEPT };
    table [S_FLOAT_A][IN_OTHER] = (struct fsm_action){ S_INVALID, A_REJECT };
    
    table [S_FLOAT][IN_INT] = (struct fsm_action){ S_FLOAT, A_CONT };
    table [S_FLOAT][IN_NULL] = (struct fsm_action){ S_ACCEPTED, A_ACCEPT};
    

    }

    void init_fsm(){
    for (int i=0; i<NUM_STATES; i++){
    for(int j=0; j<NUM_TYPES; j++){
    table[i][j] = (struct fsm_action){ S_INVALID, A_REJECT };
    }
    }
    }

    void run_machine (int current_state, int input, int *new_state, int *new_action){
    struct fsm_action tmp = table[current_state][input];
    *new_state = tmp.state;
    *new_action = tmp.action;
    }

    int get_type (char literal) {
    if (literal == '.')
    return IN_DOT;
    else if (literal == ' ')
    return IN_SPACE;
    else if(literal == '-')
    return IN_MINUS;
    else if(literal == '+')
    return IN_PLUS;
    else if (literal == 'e')
    return IN_EXP;
    else if (literal == '\0')
    return IN_NULL;
    else if (literal >= '0' && literal <= '9')
    return IN_INT;
    else
    return IN_OTHER;
    }

    bool isNumber(char* s) {
    int len = strlen(s);
    int i = 0;

    int new_state, new_action;
    int start_state = S_START;
    
    init_fsm();
    
    fsm_fill();
    
    run_machine(S_START, get_type(s[0]), &new_state, &new_action);
    
    while(new_action == A_CONT) {
        int type = get_type(s[++i]);
        
        run_machine(new_state, type, &new_state, &new_action);
    }
    if (new_action == A_ACCEPT)
        return true;
    else 
        return false;
    

    }

    }}}


Log in to reply
 

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