字符串转换函数atoi()

这道题应该使用有穷自动机来实现，如果使用单纯的逻辑分析的方法，这道题就太复杂了而且不优雅。

题目分析

首先看看输入的几种格式：

输入的内容

输入的内容可以是数字，可以是+/- 或者是空白符，或者是其他文字（四种输入）。
我们来看看中间状态，只有两种： 数字（in_number） 和 符号(signed)。因为题目中只有在输入这些之后才开始被看做是正确的内容。当输入空白符的时候，没有被视为开始，输入字母的时候直接截断。在两个中间状态的基础上，增加开始（start）和结束（end）状态，构成状态机

状态机

状态机

代码编写

按照状态机可以发现，处理的过程实质上就是当前状态（state）在接收每一个char之后的变化的过程。这里格外要注意一下越界情况就行。

public class 字符串转换数字 {
    class Solution {

//        https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/37/
        class Automaton{
            final String START = "start";
            final String SIGNED = "signed";
            final String IN_NUMBER = "in_number";
            final String END = "end";

            String state = START;
            int sign = 1;
            long ans = 0;

            HashMap<String,String[]> table = new HashMap<>();

            public Automaton(){
                table.put(START ,new String[]{START, SIGNED, IN_NUMBER, END});
                table.put(SIGNED,new String[]{END, END, IN_NUMBER, END});
                table.put(IN_NUMBER ,new String[]{END, END, IN_NUMBER, END});
                table.put(END ,new String[]{END, END, END, END});
            }

            public int get_col(char c){
                if(Character.isWhitespace(c)) return 0;
                else if (c == '+' || c == '-') return 1;
                else if (Character.isDigit(c)) return 2;
                else return 3;
            }

            public void get(char c){
                state = table.get(state)[get_col(c)];
                if(state.equals(IN_NUMBER)){
                    ans = ans * 10 + c - '0';
                    ans = sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : Math.min(ans,  - (long)Integer.MIN_VALUE);
                }else if(state.equals(SIGNED)){
                    sign = c == '+' ? 1 : -1;
                }
            }
        }

        public int myAtoi(String str) {
            Automaton automaton = new Automaton();
            for (char c: str.toCharArray()) {
                automaton.get(c);
            }
            return automaton.sign *  ((int) automaton.ans);
        }
    }
}