atoi的实现-模拟与有限自动机

摘要: 力扣8，用有限自动机识别字符串的写法

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天看一个非常经典的面试题，力扣8，atoi，将字符串转换为整数。由于本题在面试中过于常见，基本上大家都已经研究的非常透了，本文可以当个复习看看。

本题除了按要求模拟以外，还可以用自动机来解决。我们首先给出模拟的算法，然后构造自动机来识别字符串中的整数，最后给出的代码可以作为用自动机识别字符串的模板使用。

---

题目

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

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

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

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

注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

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

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

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

---

题解

算法1: 模拟

按照要求模拟即可，难点是分类讨论，以及边界情况，整体思路如下:

1. 丢弃开头的空字符
2. 第一个非空字符为有效整数字符(+-数字), 则与后续尽可能多的数字连起来
3. 除有效整数部分之外，后续的字符忽略即可，不应对结果有影响
4. 这三种情况不需要进行转换：<1>空串，<2>仅含空字符的串，<3>第一个非空字符不是有效整数字符。
5. 任何无法有效转换的情况返回 0
6. 爆INT时，根据正负返回 `INT_MIN` 或者 `INT_MAX`
7. 仅 `' '` 认为是空字符

以一个 int result 在遍历数字的阶段保存结果，初始是 0。每遍历到一个待加入到结果里的数字 iter, result 就更新为 result = result * 10 + iter。

上面这一步公式是整个过程唯一可能会可能会爆 int 的地方，在执行之前，需要加一步判断。也就是这个式子 result > (INT_MAX - iter) / 10 如果成立的话，则上面的式子会爆 int，直接根据正负直接返回 INT_MAX 或是 INT_MIN。

如果正常出了循环，说明此时的 result 在 [0, 2^32-1] 范围之内，不会再有爆 int 的情况，按照正负输出结果即可。

代码(C++)

class Solution {
public:
    int myAtoi(string str) {
        if(str.empty())
            return 0; // 空串的情况
        int n = str.size();

        int sign = 1;
        int start = 0; // 第一个非空字符的位置
        for(; start < n; ++start)
            if(str[start] != ' ')
                break;
        if(start == n)
            return 0; // 仅含空字符的情况
        if(!is_digit(str[start]) && !is_sign(str[start]))
            return 0; // 第一个非空字符不是有效整数字符的情况
        if(is_sign(str[start]))
        {
            if(str[start] == '-')
                sign = -1;
            ++start;
        }

        int result = 0;
        // 一上来 start 就等于 n 是 +- 号之后紧跟着非数字的情况，不进循环, result 为 0 不变
        while(start < n && is_digit(str[start]))
        {
            int iter = str[start] - '0';
            if(result > (INT_MAX - iter) / 10)
            {
                if(sign == 1)
                    return INT_MAX;
                else
                    return INT_MIN;
            }
            result = result * 10 + iter; // 这里有可能溢出，以上是处理
            ++start;
        }
        if(sign == 1)
            return result;
        else
            return -result;
    }

private:
    bool is_digit(const char &c)
    {
        return c - '0' >= 0 && c - '0' <= 9;
    }

    bool is_sign(const char &c)
    {
        return (c == '+') || (c == '-');
    }
};

算法2：有限自动机

有限自动机的理论可以参考编译原理的书，这里直接进行应用。

记 DFA $M = (S, \Sigma, f, S_{0}, F)$。

状态集合

首先看状态集合 $S$。

-1: 非法状态  
0: 起始的空格  
1: 起始的+-  
2: 整数，例如(9, -11, +191)

字母表

再看字母表 $\Sigma$。

空格
+-
0123456789
非法字符

初始状态

初始状态 $S_{0} = 0$

终结状态

终结状态 $F = \{2, 3\}$

状态转换图

DFA 从状态 0 开始逐字符读字符串，一边读一边更新结果。

在某字符处状态转移后，若所得状态非法，直接返回此时的结果，否则继续读下一字符，直至字符串耗尽。

当字符串耗尽，返回此时的结果。

状态转移函数 $f$ 以状态转换图表示。

代码 (C++)

class Solution {
public:
    int myAtoi(string str) {
        if(str.empty()) return 0;
        int n = str.size();
        int state = 0;
        vector<bool> finals({0, 0, 1});
        vector<vector<int>> transfer({
                {0,  1,  2, -1},
                {-1, -1, 2, -1},
                {-1, -1, 2, -1},
                });

        int sign = 1;
        long long ans = 0;
        for(int i = 0; i < n; ++i)
        {
            state = transfer[state][_make(str[i])];
            if(state < 0)
                return sign * ans;
            if(state == 1 && str[i] == '-')
                sign = -1;
            if(state == 2)
            {
                ans *= 10;
                ans += str[i] - '0';
            }
            if(ans * sign <= INT_MIN)
                return INT_MIN;
            if(ans * sign >= INT_MAX)
                return INT_MAX;
        }
        return sign * ans;
    }

private:
    int _make(const char& c)
    {
        switch(c)
        {
            case ' ': return 0;
            case '+': return 1;
            case '-': return 1;
            default: return _number(c);
        }
    }

    int _number(const char& ch)
    {
        if(ch >= '0' && ch <= '9')
            return 2;
        else
            return 3;
    }
};

---