字符串转换整数 (atoi)

## 1 题目

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

* 读入字符串并丢弃无用的前导空格
* 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
* 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
* 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
* 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
* 返回整数作为最终结果。

**注意：**

* 本题中的空白字符只包括空格字符 ' ' 。
* 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

**示例 1：**

```txt
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
```

**示例 2：**

```txt
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
```

**示例 3：**

```txt
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
```

**示例 4：**

```txt
输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
         ^
解析得到整数 0 ，因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
```

**示例 5：**

```txt
输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
          ^
第 3 步："-91283472332"（读入 "91283472332"）
                     ^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。提示：0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
```

## 2 解题思路

### 2.1 有限状态机

#### 2.1.1 含义

1. 有限状态机是一种用来进行**对象行为建模**的工具，其作用主要是**描述对象在他的生命周期内所经历的状态序列**，**以及如何响应来自外界的各种事件**。
2. 在计算机科学中，有限状态机被广泛用于**建模应用行为**、**硬件电路系统设计**、**软件工程**、**编译器**、**网络协议**、**计算机与语言的研究**，比如下图非常有名的 TCP 协议状态机：![](/media/202107/2021-07-12_2119070.18551046937634952.png)
3. 我们在编程时实现相关业务逻辑时经常需要**处理各种事件和状态切换**，写各种 `switch/case` 和 `if/else`，所以我们其实可能一直都在跟有限状态机打交道，只是可能没有意识到。
4. 在处理一些**业务逻辑比较复杂**的需求时，可以先看看**是否适用于用一个有限状态机来描述**，如果可以**把业务模型抽象成一个有限状态机**，那么**代码逻辑就会特别清晰**，**结构特别规整**。
5. 状态机主要包括四个要素，分别是**现态**、**条件**、**动作**、**次态**，**现态和条件是因**，**动作和次态是果**，具体如下：
   1. **现态**：指**当前所处状态**。
   2. **条件**：又称**事件**，当**一个条件满足**时，就**会触发一个动作**，**或者执行一次状态的迁移**。
   3. **动作**：指**条件满足后执行的动作**，**动作执行完毕后**，**可以迁移到新的状态**，**也可以仍旧保持原状态**，动作**不是必需的**，当条件满足后，**也可以不执行任何动作**，**直接迁移到新状态**。
   4. **次态**：指**条件满足后要迁往的新状态**，次态是相对于现态而言的，**次态一旦被激活**，**就转变成新的现态了**。
6. 我们可以用**状态表**表示整个过程，如下图所示：![](/media/202107/2021-07-12_2131210.030304143730127353.png)

#### 2.1.2 问题分析

1. 该题目如果要用 `if ... else` 或 `switch ... case` 来判断的话将会非常麻烦，而且情况我们可能也不会考虑的那么全面，因此有可能我们调试了很长时间还是无法提交通过。
2. 这时候我们可以采用一种叫做[有限状态机](#2-1-有限状态机)的方式来解决，具体的**状态表**如下表所示：

|           | " "   | +/-    | 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   |

3. 下面以第一行为例说明一下上面表格表示的含义，最左边的 `start` 表示初始状态：
   1. 当遇到" "时，状态更新为 `start`。
   2. 当遇到 `+/-` 时，状态更新为 `signed`。
   3. 当遇到 `number` 时，状态更新为 `in_number`。
   4. 当遇到 `other` 时，状态更新为 `end`。
4. 因此可以**对字符串 $s$ 中的字符 $c$ 进行逐个遍历**，然后**根据字符的值确定当前状态 $state$**，然后**根据相应的状态完成相应的动作**，假设用 $ans$**表示最后的结果**，**初始值为 0**，$sign$**表示最后的结果的符号**，**1 表示正号**，**-1 表示负号**：
   1. 当 $state$ 为 `in_number` 时，说明当前字符 $c$ 为**数字**，则：
      1. `ans = 10 * ans + c - '0'`。
      2. `ans = (sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE))`。
   2. 当 $state$ 为 `signed` 时，表示当前字符 $c$ 为**符号**，则：
      1. `sign = (c == '-' ? -1 : 1)`。
5. 当**字符串遍历完成**后，直接返回**符号和结果的乘积**$sign * ans$ 即可。

#### 2.1.3 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/7/12 20:41
 * @Description 字符串转换整数 (atoi)
 */
public class L8 {
    /**
     * 8. 字符串转换整数 (atoi)
     *
     * @param s 字符串
     * @return 字符串对应的整数
     */
    public int myAtoi(String s) {
        //  定义有限状态机
        Automaton automaton = new Automaton();
        for (int i = 0; i < s.length(); i++) {
            //  执行有限状态机中的方法，完成相应的状态转移
            automaton.get(s.charAt(i));
        }
        //  将符号和数值相乘，作为最后的结果返回
        return (int) (automaton.sign * automaton.ans);
    }

/**
     * 有限状态机
     */
    class Automaton {
        public int sign = 1;    /*符号*/
        public long ans = 0;    /*数值*/
        private String state = "start"; /*状态*/
        private Map<String, String[]> table = new HashMap<String, String[]>() {
            {
                put("start", new String[]{"start", "signed", "in_number", "end"});
                put("signed", new String[]{"end", "end", "in_number", "end"});
                put("in_number", new String[]{"end", "end", "in_number", "end"});
                put("end", new String[]{"end", "end", "end", "end"});
            }
        };  /*状态表*/

/**
         * 状态转移方法
         * @param c 当前字符
         */
        public void get(char c) {
            state = table.get(state)[get_col(c)];
            if ("in_number".equals(state)) {
                //  当前状态为数值，因此进行数值相应的计算
                ans = 10 * ans + c - '0';
                //  当 sign == 1 时，说明此时为正数，因此取 ans 和 Integer.MAX_VALUE 的最小值
                //  否则，说明此时为负数，因此取 ans 和 -Integer.MIN_VALUE 的最小值（现在求的只是数值大小，符号后面会统一加）
                ans = (sign == 1 ? Math.min(ans, Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE));
            } else if ("signed".equals(state)) {
                //  当前状态为符号，因此判断最后是否需要乘以 -1
                sign = (c == '-' ? -1 : 1);
            }
        }

/**
         * 获取有限状态表中的状态
         * @param c 字符
         * @return  字符对应于有限状态表中的状态
         */
        public int get_col(char c) {
            if (c == ' ') {
                //  start
                return 0;
            } else if (c == '+' || c == '-') {
                //  signed
                return 1;
            } else if (Character.isDigit(c)) {
                //  in_number
                return 2;
            } else {
                //  end
                return 3;
            }
        }
    }
}
```

## 3 参考文献

1. [8. 字符串转换整数 (atoi)](https://leetcode-cn.com/problems/string-to-integer-atoi)。
2. [字符串转换整数 (atoi)](https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-)。
3. [深入浅出理解有限状态机](https://zhuanlan.zhihu.com/p/46347732)。