State machine-based JS solution


  • 0
    P

    A simple state diagram was drawn up based on the problem instructions:

    state diagram

    This state machine (and a character queue) is used below to process input. States with no outbound transitions are assumed to loop on any input.

     * @param {string} str
     * @return {number}
     */
    var myAtoi = function(str) {
        //some constants
        var DIGIT = "DIGIT";
        var SIGN = "SIGN";
        var WHITESPACE = "WHITESPACE";
        var OTHER = "OTHER";
        
        var MAX_INT = 2147483647;
        var MIN_INT = -2147483648;
    
        //some helper functions
        var isDigit = function(s) {
            return /^\d$/.test(s);
        };
        var isSignChar = function(s) {
            return /^[+\-]$/.test(s);
        };
        var isWhiteSpace = function(s) {
            return /^\s$/.test(s);
        };
        
        var charType = function(s) {
            if (isDigit(s)) return DIGIT;
            if (isSignChar(s)) return SIGN;
            if (isWhiteSpace(s)) return WHITESPACE;
            return OTHER;
        }
        var numStart = -1, numEnd = -1;
        
        var states = {};
        
        //state: initial
        states.i = {
            DIGIT: "a",
            SIGN: "s",
            WHITESPACE: "i",
            OTHER: "0",
            valid: false
        };
        
        //state: saw 0 or more whitespace and a sign character
        states.s = {
            DIGIT: "a",
            SIGN: "0",
            WHITESPACE: "0",
            OTHER: "0",
            valid: false
        };
        
        //state: accumulator
        states.a = {
            DIGIT: "a",
            SIGN: "r",
            WHITESPACE: "r",
            OTHER: "r",
            valid: true,
        };
        
        //state: trap state, invalid input, return 0
        states[0] = {
            DIGIT: "0",
            SIGN: "0",
            WHITESPACE: "0",
            OTHER: "0",
            valid: false
        };
        
        //state: trap state, saw valid input followed by garbage
        states.r = {
            DIGIT: "r",
            SIGN: "r",
            WHITESPACE: "r",
            OTHER: "r",
            valid: true
        };
        
        var state = states.i;
        
        var queue = [];
        for (var i = 0; i < str.length; i++) {
            var c = str[i];
            var type = charType(c);
            
            //transition to the appropriate state
            state = states[state[type]];
            
            //these are our push states, accumulate input on the queue
            if (state == states.s || state == states.a) {
                queue.push(c);
            }
        }
        
        //input wasn't valid, return 0
        if (!state.valid) {
            return 0;
        }
        
        //convert the queue to an integer
        //our queue is gauranteed by the state machine to contain:
        //1. 0 or 1 sign symbols followed by
        //2. 0 or more digits
        var result = 0;
        var sign = "+";
        while (queue.length > 0) {
            var d = queue.shift();
            
            //for digits, do standard accumulation technique
            if (isDigit(d)) {
                result = result * 10 + parseInt(d);
                
                //simulated overflow, or real overflow
                if (result > MAX_INT || result < 0) {
                    if (sign == "+")
                        return MAX_INT;
                    else
                        return MIN_INT;
                }
            //for sign characters, just update the sign
            } else if (isSignChar(d)) {
                if (d == "-")
                    sign = "-";
            }
        }
        
        //convert to appropriate sign if necessary
        if (sign == "-")
            result = result * (-1);
            
        return result;
    };

Log in to reply
 

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