编程之禅
0%

字符串转整数——自动机

发表于 更新于 分类于 阅读次数： Disqus：

题目链接

请你来实现一个 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:

1
2
输入：s = "42"
输出：42

示例2:

1
2
输入：s = "   -42"
输出：-42

示例3:

1
2
输入：s = "4193 with words"
输出：4193

示例4:

1
2
输入：s = "words and 987"
输出：0

示例5:

1
2
输入：s = "-91283472332"
输出：-2147483648

方法一

首先识别出字符串中的数字，并记录其正负。从低位到高位，对于每一个字符 c，用 c - ‘0’ 得到实际数字值，对于所有数字累加：ans = ans*10 + c-'0'，ans 是 int 类型，需要注意溢出问题。ans*10会溢出，ans*10 + c-‘0’也会溢出。判断方法：

1
2
3
4
5
6
int num = c-'0';
if(ans > INT_MAX/10 || (ans==INT_MAX && num>7)){
		// 溢出
}else{
  	ans = ans*10 + c-'0'
}

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    int myAtoi(string s) {
      	// first 和 last 记录数字范围
        int first = 0;
        int last = 0;
        bool ispositive = false;   // 是否为负
        int ans = 0;
        
        // 去除前导0
        for(; first<s.length(); ++first){
            if(s[first]!=' ')
                break;
        }

        // 判断正负号
        if(s[first]=='-'){
                ispositive=true;
                ++first;
        }else if(s[first]=='+'){
                ++first;
        }
        
       // 判断数字
       if(s[first]<'0' || s[first]>'9'){
           return 0;
       }

       // 去除前导0
       for(; first<s.length(); ++first){
            if(s[first]!='0')
                break;
       }

        // 找到第一个非数字符号
        for(int i=first; i<s.length(); ++i){
            if(s[i]<'0' || s[i]>'9'){
                break;
            }else{
                last = i;
            }
        }

        for(int i=first; i<=last; ++i){
            int num = s[i]-'0';
            if(ans > INT_MAX/10 || (ans==INT_MAX/10 && num>7))
                return ispositive?INT_MIN:INT_MAX;
            else 
                ans = ans*10 + num;
        }

        if(ispositive){
            return -ans;
        }else{
            return ans;
        }
    }
};

可以看到代码容易写的比较臃肿，接下来介绍自动机方法。

方法二

自动机法。本方法使用的自动机，也叫有限状态自动机，它包含多种状态，有开始状态，也有结束状态，一个状态可以跳转到其他状态。从开始状态开始，经过状态的改变来到结束状态。

使用自动机：可以识别特定的符号，当然它也可以在字符串中识别数字。

如下图所示自动机：

截屏2021-09-17 下午11.35.15

start 表示开始状态，end 表示结束状态

start 表示开始状态，开始状态遇到 ‘空格’ 还是start 状态(相当于去掉前导0)；遇到数字，就跳转到 in_number 状态；遇到+/-号，就跳转到 signed；遇到其他字符就进入 end 状态(表示无数字)。

signed 遇到数字，进入 in_number(开始处理数字)，遇到其它非数字符号，就进入 end 状态。

in_number 遇到数字还是 in_number；遇到其它字符，说明已经处理完数字，直接进入 end 。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Automata{
    string state = "start";
    unordered_map<string,vector<string>> 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"}}
    };

    int get_col(char c){
        if(isspace(c)) return 0;
        if(c=='+'||c=='-') return 1;
        if(isdigit(c)) return 2;
        return 3;
    }

public:
    int sign = 1;
    long long ans = 0;
    void get(char c){
        state = table[state][get_col(c)];
        if(state=="in_number"){
            ans = ans*10 + c-'0';
            ans = sign==1 ? min(ans,(long long)INT_MAX): min(ans,-(long long)INT_MIN);
        }else if(state == "signed"){
            sign = c=='+'?1:-1;
        }
    }
};

class Solution {
public:
    int myAtoi(string s) {
        Automata automata;
        for(char c:s){
            automata.get(c);
        }
        return automata.sign * automata.ans;
    }
};

上述代码使用自动机扫描字符串，并识别其中的数字和正负号。代码中使用 long long 类型，它是 64 位系统独有的，不适用于 32 位系统。为了提高兼容性，接下来给出 适用于 32 位系统的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Automata{
    string state = "start";
    unordered_map<string,vector<string>> 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"}}
    };

    int get_col(char c){
        if(isspace(c)) return 0;
        if(c=='+'||c=='-') return 1;
        if(isdigit(c)) return 2;
        return 3;
    }

public:
    int sign = 1;
    int ans = 0;
    bool finish = true;   // 标记是否已经达到最大值，为 true 表示未达到最大值
    void get(char c){
        state = table[state][get_col(c)];
        if(state=="in_number"){
            int num = c-'0';
            if(ans > INT_MAX/10 || (ans==INT_MAX/10 && num>7)){
                ans = sign==1?INT_MAX:INT_MIN;
                finish = false;
            }else if(finish==true){
                ans = ans*10 + num; 
            }
        }else if(state == "signed"){
            sign = c=='+'?1:-1;
        }
    }
};




class Solution {
public:
    int myAtoi(string s) {
        Automata automata;
        for(char c:s){
            automata.get(c);
        }
        
        if(automata.finish)
            return automata.ans * automata.sign;
        else
            return automata.ans;
    }
};