编译原理没好好听（不如说脑子里没有那种思维），现在要遭重啦！

题目介绍

这道题要求实现 atoi 函数，它要求将一个字符串转成整型，并且有以下要求——

如果转换失败，返回 0
忽略不限数量的前置零
能判断正负
有效的整数后可能有非法字符，应当能够处理所有有效整数
如果整型溢出，则返回整型的最大值或最小值

比如，对输入“ -42”，返回-42，对输入“ +43hello”，返回 43，对”he is a 5”，返回 0

我的实现——一万个条件判断

这里是我之前写的代码——

首先检查输入，如果输入为空，或者长度为 1，则直接返回结果。

然后排除前置零，找到第一个非零元素。判断该元素是否是+，-或数字。

然后找到数字的第一个有效位置，从此处开始找到数字的最后一个有效位置。

此时，数字的符号，开始位置和结束位置已经决定，下面就不言自明了。

关于溢出的判断，可以看到每次递增都是 res = res * 10 + temp，在计算前对 res 进行判断。

对于正数，需要看是否大于 MAX_VALUE/10，如果大于，则必定越界。如果等于，则判断 temp 是否小于 7（整型的上界的个位是 7），如果 temp 小于 7 则不越界，如果其小于 MAX_VALUE/10 则也不越界。

负数遵循相似的判断方法，如果 temp 小于-8（整型的下界的个位是 8），则必定越界。

int myAtoi(String s) {
    //对输入进行判断
    if (s.isEmpty())
        return 0;
    else if (s.length()==1) { // 长度为 1
        int temp = s.charAt(0) - '0';
        if (temp>=0 && temp<=9)
            return temp;
        return 0;
    }

    // 首先找到第一个不为空格的元素，如果这个 char 不是-,+或数字，则返回 0，否则继续操作
    int pointer = 0; // 指向第一个非 whitespace 的数

    // 首先找到第一个非 space 的元素
    while (s.charAt(pointer) == ' ') { 
        pointer++;
        if (pointer == s.length())
            return 0; // 全为空格
    }
    char first = s.charAt(pointer);

    // 检查这第一个非 space 的元素是否是数字或+,-，如果不是则转换失败
    if (!(Character.isDigit(first) || first == '-' || first == '+'))
        return 0;

    // 判断正负。如果有正负号，则应当将 pointer++，指向第一个数字
    boolean positive = true; // 判断正负
    if (first == '-') {
        positive = false;
        pointer++;
    } 
    else if (first == '+')
        pointer++;

    if (!Character.isDigit(s.charAt(pointer)))
        return 0;
    // 正负已经被 positive 确定，pointer 指向第一个数字（也或许不是数字）了，现在获取最后一个有效数字
    int end;
    for (end = pointer; end < s.length() && Character.isDigit(s.charAt(end)); end++); 
    // 这时候 end 可能为数组长度 s.length()，或者是数字的最后一个元素的后一个元素
    end--; //现在 end 是数字的最后一个元素了

    // 已经知晓有效数字的开始位置 start，结束位置 end，正负 positive
    int res = 0;
    for (int i = pointer; i <= end; i++) {
        int temp = s.charAt(i) - '0';
        if (!positive) temp = -temp;
        if (res > Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && temp > 7) 
            return Integer.MAX_VALUE; // 判断是否溢出。为什么是 temp > 7？ 因为整型最大值的个位数是 7
        if (res < Integer.MIN_VALUE/10 || res == Integer.MIN_VALUE/10 && temp < -8) 
            return Integer.MIN_VALUE;
        res = res * 10 + temp;
    }
    return res;
}

可以看到，这个实现是非常……臃肿的，代码并不好修改（也不好看），if 和 return 到处都是。虽然我 no bug AC 了，但是这绝对是机缘巧合。这样多分支的玩意出现 bug 轻而易举。

于是去翻了下题解，卧槽？DFA？还有这种操作？原来这种流程复杂的玩意可以用自动机优雅地解决……我是没想到编译原理里的东西可以用到这里……这必须得学习一波了。

DFA 的实现

状态转移图如下，start 为初始，signed 为判断正负，in_number 则是正在处理有效数字，end 为转换失败或转换完成

然后贴上状态转移表。这个表描述任意条件下遇到各种字符的处理方法。比如在 start 条件下，遇到 number 则跳转到 in_number 下

	‘ ‘	+/-	number	other
start	start	signed	in_number	end
signed	end	end	in_number	end
in_number	end	end	in_number	end
end	end	end	end	end

总之先贴上题解的 python 代码——

INT_MAX = 2 ** 31 - 1
INT_MIN = -2 ** 31

class Automaton:
    def __init__(self):
        self.state = 'start' // 代表当前状态
        self.sign = 1 // 代表符号
        self.ans = 0 // 代表结果
        self.table = { // 状态转移表
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }
        
    def get_col(self, c): // 根据字符来获取状态转移表的列
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3

    def get(self, c): // 根据字符进行操作。注意，是先更改状态，再进行操作
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, str: str) -> int:
        automaton = Automaton()
        for c in str: // 遍历字符串
            automaton.get(c) 
        return automaton.sign * automaton.ans

下面默写一次 java 版本！

class Automation {
    enum State {
        START, SIGNED, IN_NUMBER, END
    }
    int sign = 1;
    public int res = 0;
    State state;
    HashMap<State, State[]> table;

    public Automation() {
        state = State.START;
        table = new HashMap<State, State[]>();
        table.put(State.START, new State[] { State.START, State.SIGNED, State.IN_NUMBER, State.END });
        table.put(State.SIGNED, new State[] {State.END, State.END, State.IN_NUMBER, State.END});
        table.put(State.IN_NUMBER, new State[] {State.END, State.END, State.IN_NUMBER, State.END});
        table.put(State.END, new State[] { State.END, State.END, State.END, State.END });
    }
    private int get_col(char c) {
        if (c == ' ')
            return 0;
        if (c == '+' || c == '-')
            return 1;
        if (Character.isDigit(c))
            return 2;
        return 3;
    }
    public void get(char c) { // 每一个状态进行什么处理在这里实现
        state = table.get(state)[get_col(c)]; //state 转到下一个状态
        if (state == State.SIGNED) 
            sign = c=='+'? 1: -1; //从+/-判断正负
        if (state == State.IN_NUMBER) {
            //首先判断 ans*10 再加上这个数是否越界
            int temp = (c - '0') * sign;
            if (res > Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && temp > 7) {
                res = Integer.MAX_VALUE;
                state = State.END; // 越界了，强行将状态置为 END
                return;
            }
            if (res < Integer.MIN_VALUE/10 || res == Integer.MIN_VALUE/10 && temp < -8) {
                res =  Integer.MIN_VALUE;
                state = State.END;
                return;
            }
            res = res * 10 + temp;
        }
    }
}

public class Solution {
	public static int myAtoi(String s) {
        Automation automation = new Automation();
        for (char c: s.toCharArray())
            automation.get(c);
        return automation.res;
    }
}

总之学习了！

举一反三——isValidNumber

不实践，如何敢说自己掌握了？

这一题，要求判断一个数字字符串是否为合法数字。合法字符串应当只包括如下内容（以及前置后置空格）——

数字 0 到 9
指数 e （科学计数法的那个玩意）
正负号-/+
小数点。

数字可以分为三个部分——数字，指数符号 e，指数，其中数字可以有正负和小数点，如-43.2。指数是可选的，但是如果有 e，则必须要有指数。其中指数必须为整数，可以有正负号，比如-43.2e-10…

然而题目告诉我，像。1 这样的也合法，wtf？

于是，容易画出状态转移图——

不画了，有点麻烦（没有舒服的软件可用）……草稿纸上手画后直接写状态转移表（这个有问题）——

	WHITESPACE	+/-	number	.	e	other
START	START	SIGN	INTEGER	DECIMAL_POINT	ERROR	ERROR
SIGN	ERROR	ERROR	INTEGER	DECIMAL_POINT	ERROR	ERROR
INTEGER	END	ERROR	INTEGER	DECIMAL_POINT	E	ERROR
DECIMAL_POINT	END	ERROR	DECIMAL	ERROR	E	ERROR
DECIMAL	END	ERROR	DECIMAL	ERROR	E	ERROR
E	ERROR	E_SIGN	E_NUMBER	ERROR	ERROR	ERROR
E_SIGN	ERROR	ERROR	E_NUMBER	ERROR	ERROR	ERROR
E_NUMBER	END	ERROR	E_NUMBER	ERROR	ERROR	ERROR
END	END	ERROR	ERROR	ERROR	ERROR	ERROR
ERROR	ERROR	ERROR	ERROR	ERROR	ERROR	ERROR

这里需要注意的是，-.1e10 是合法的，-1.e10 是合法的，但是-.e10 是不合法的，1. 是合法的，.1 是合法的，但。是不合法的，因此显然需要保存是否已经检测到数字……

不过可以定两个小数点的状态，让 start->dot->digit 和 start->digit->dot 两条路径不经过同一个 dot 状态，就如下面官方题解给出的状态转移表……这样也不需要做多余判定了。两个状态可以叫做 POINT_WITH_INT 和 POINT_WITHOUT_INT

下面是实现——

class Automation {
    enum State {
        START, SIGN, INTEGER, DECIMAL_POINT, DECIMAL, E, E_SIGN, E_NUMBER, END, ERROR
    }

    boolean flag;
    State state;
    HashMap<State, State[]> table;

    public Automation() {
        state = State.START;
        flag = false;
        table = new HashMap<State, State[]>();
        table.put(State.START,
                new State[] { State.START, State.SIGN, State.INTEGER, State.DECIMAL_POINT, State.ERROR, State.ERROR });
        table.put(State.SIGN,
                new State[] { State.ERROR, State.ERROR, State.INTEGER, State.DECIMAL_POINT, State.ERROR, State.ERROR });
        table.put(State.INTEGER,
                new State[] { State.END, State.ERROR, State.INTEGER, State.DECIMAL_POINT, State.E, State.ERROR });
        table.put(State.DECIMAL_POINT,
                new State[] { State.END, State.ERROR, State.DECIMAL, State.ERROR, State.E, State.ERROR });
        table.put(State.DECIMAL,
                new State[] { State.END, State.ERROR, State.DECIMAL, State.ERROR, State.E, State.ERROR });
        table.put(State.E,
                new State[] { State.ERROR, State.E_SIGN, State.E_NUMBER, State.ERROR, State.ERROR, State.ERROR });
        table.put(State.E_SIGN,
                new State[] { State.ERROR, State.ERROR, State.E_NUMBER, State.ERROR, State.ERROR, State.ERROR });
        table.put(State.E_NUMBER,
                new State[] { State.END, State.ERROR, State.E_NUMBER, State.ERROR, State.ERROR, State.ERROR });
        table.put(State.END,
                new State[] { State.END, State.ERROR, State.ERROR, State.ERROR, State.ERROR, State.ERROR });
        table.put(State.ERROR,
                new State[] { State.ERROR, State.ERROR, State.ERROR, State.ERROR, State.ERROR, State.ERROR });
    }

    private int get_col(char c) {
        if (c == ' ')
            return 0;
        if (c == '+' || c == '-')
            return 1;
        if (Character.isDigit(c))
            return 2;
        if (c == '.')
            return 3;
        if (c == 'e')
            return 4;
        return 5;
    }

    public void get(char c) { // 每一个状态进行什么处理在这里实现
        state = table.get(state)[get_col(c)]; // 转到下一个状态
        // ... 好像没有要做的处理的亚子
        if (state == State.INTEGER || state == State.DECIMAL)
            flag = true; // 考虑到有 1. .3 这样的数字是合法，而一个小数点是非法的……必须得暂存起来了
    }

    public boolean isValid() {
        // 需要考虑合法的终结状态有 DECIMAL_POINT，INTEGER,DECIMAL，E_NUMBER 和 END，其他状态结束都是非法的，然后要考虑以小数点结束时，是否已经有合法数字了
        return  flag && (
                state == State.INTEGER ||
                state == State.DECIMAL_POINT ||
                state == State.DECIMAL || 
                state == State.E_NUMBER || 
                state == State.END);
    }
}
class Solution {
    public boolean isNumber(String s) {
        Automation automation = new Automation();
        for (char c : s.toCharArray())
            automation.get(c);
        return automation.isValid();
    }
}

然后看题解，wtf？路漫漫其修远兮啊……

舒服多了，也不需要一个额外的 bool 值来让代码变丑，最终也只需要判断最后是不是状态 3,5,6,8（8 由状态 3,5,6 跳转，负责判断有没有后置 0）……

下面重写一次状态转移表，就不再实现了。

	space	+/-	number	.	e	other
START	START	SIGN	NUMBER	DOT_WITHOUT_INT	ERROR	ERROR
SIGN	ERROR	ERROR	NUMBER	DOT_WITHOUT_INT	ERROR	ERROR
NUMBER	END	END	NUMBER	DOT_WITH_INT	E	ERROR
DOT_WITH_INT	END	ERROR	NUMBER	ERROR	E	ERROR
DOT_WITHOUT_INT	ERROR	ERROR	NUMBER	ERROR	ERROR	ERROR
E	ERROR	E_SIGN	E_NUMBER	ERROR	ERROR	ERROR
E_SIGN	ERROR	ERROR	E_NUMBER	ERROR	ERROR	ERROR
E_NUMBER	END	ERROR	E_NUMBER	ERROR	ERROR	ERROR
END	END	ERROR	ERROR	ERROR	ERROR	ERROR
ERROR	ERROR	ERROR	ERROR	ERROR	ERROR	ERROR

NUMBER，DOT_WITHOUT_INT，E_NUMBER 和 END 是终结状态，如果最终自动机处于这几个状态，则识别成功。

算法 NFA

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议，转载请注明出处！

概观 java 的面向对象上一篇

关于一些世界语的学习资源下一篇

自动机——我的 atoi 函数

题目介绍

我的实现——一万个条件判断

DFA 的实现

举一反三——isValidNumber