Leetcode - 8. 字符串转换整数 (atoi)

class Solution {

    // 使用自动机来解决，具体的解题思路可以参考官方题解
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        for (char c : str.toCharArray()) {
            automaton.transform(c);
            if (automaton.isEnd()) {
                break;
            }
        }
        return automaton.getFinalResult();
    }
}

class Automaton {

    // 一个重要的值：-214748364，是判断是否溢出的重要依据
    private static final int THRESHOLD = Integer.MIN_VALUE / 10;

    // 用数字来表示字符类型和状态机状态
    private static final int BLANK = 0, SIGN = 1, NUM = 2, OTHER = 3;
    private static final int START = 0, SIGNED = 1, NUMBER = 2, END = 3;

    // 获取字符类型
    private static int getCharType(char c){
        if (c == ' ') return BLANK;
        if (c == '+' || c == '-') return SIGN;
        if (c >= '0' && c <= '9') return NUM;
        return OTHER;
    }

    // 状态转换表
    private static final int[][] TRANSFORM = new int[4][4];
    static {
        TRANSFORM[START][BLANK] = START;
        TRANSFORM[START][SIGN] = SIGNED;
        TRANSFORM[START][NUM] = NUMBER;
        TRANSFORM[START][OTHER] = END;

        TRANSFORM[SIGNED][BLANK] = END;
        TRANSFORM[SIGNED][SIGN] = END;
        TRANSFORM[SIGNED][NUM] = NUMBER;
        TRANSFORM[SIGNED][OTHER] = END;

        TRANSFORM[NUMBER][BLANK] = END;
        TRANSFORM[NUMBER][SIGN] = END;
        TRANSFORM[NUMBER][NUM] = NUMBER;
        TRANSFORM[NUMBER][OTHER] = END;

        TRANSFORM[END][BLANK] = END;
        TRANSFORM[END][SIGN] = END;
        TRANSFORM[END][NUM] = END;
        TRANSFORM[END][OTHER] = END;
    }

    // 这两个用于存储最终结果的正负性和绝对值（这里用负数存储绝对值，因为负数的表示范围更大）
    private int sign = 1, resultNegAbs = 0;

    // 用该变量表示是否已经出现了溢出
    // 如果溢出了，那么最终输出结果将是Integer的最大/小值（由sign来决定），而与resultNegAbs无关
    private boolean overflow = false;
    
    private int state = START;
    public boolean isEnd() {
        return state == END;
    }

    // 获取最终结果
    public int getFinalResult(){
        if (!overflow) {
            return sign * resultNegAbs * -1;
        }
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    }

    // 读取进一个字符后，自动机会转换到另一个状态
    public void transform(char c) {

        // 转换到新状态，并且转换到新状态后，还需要进行相应的操作
        switch (state = TRANSFORM[state][getCharType(c)]){

            // 如果转到START/END状态，则什么都不用做
            case START: 
            case END:
                break;

            // 如果转到了SIGNED状态，则改变成员sign的值
            case SIGNED: {
                sign = (c == '+' ? 1 : -1);
                break;
            }

            // 如果转到了NUMBER状态，则需要将读取到数字累加到resultNegAbs * 10中
            case NUMBER: {
                int i = c - '0';

                // 累加前先判断是否会导致溢出
                checkOverflowAfterAddANum(i);

                // 这里可以放心地累加上去，因为overflow已经被设置了，而它的优先级比resultNegAbs高
                resultNegAbs = resultNegAbs * 10 - i;

                break;
            }
        }
    }

    // 判断将数字i累加到resultNegAbs * 10中是否会发生正/负溢出
    private void checkOverflowAfterAddANum(int i){

        // 如果已经溢出了，则添加数字i后还是溢出，因此直接返回
        if (overflow) return;

        // 如果resultNegAbs不等于-214748364
        // 那么如果是小于则溢出，是大于则不会溢出
        if (resultNegAbs != THRESHOLD) {
            overflow = resultNegAbs < THRESHOLD;

        // 如果resultNegAbs正好等于-214748364
        // 那么还需要根据sign和i来判断是否溢出
        } else{
            overflow = i > (sign == 1 ? 7 : 8);
        }
    }
}