这一题可以通过自动机（DFA）的方法解答，DFA方法实际上就是通过状态转移的方式解答。
根据题目，我们可以把求解过程分为四个状态：
-
初始状态 – start – 0
-
符号状态 – sign – 1
-
数字状态 – num – 2
-
终止状态 – end – 3
将这四个状态分别记为0,1,2,3 。程序从初始状态0开始，当运行到终止状态3就停止。
从初始状态开始，遍历字符串s。读取到的字符有四种情况：空格、符号位、数字、其他字符。
在各个状态遇到这四种字符时：
-
初始状态0
-
遇到空格，则状态不变，直接读取下一个字符；
-
遇到符号位，记录读取到的符号，并将状态切换为符号状态1；
-
遇到数字，记录下数字，并将状态切换为数字状态2；
-
遇到其他字符，将状态切换为终止状态3。
-
符号状态1
-
遇到空格，将状态切换为终止状态3；
-
遇到符号位，将状态切换为终止状态3；（当s=”+-12″时，输出应为0，所以碰到两个符号位要终止）
-
遇到数字，记录下数字，并将状态切换为数字状态2；
-
遇到其他字符，将状态切换为终止状态3。
-
数字状态2
-
遇到空格，将状态切换为终止状态3；
-
遇到符号位，将状态切换为终止状态3；
-
遇到数字，记录下数字，状态不变；
-
遇到其他字符，将状态切换为终止状态3。
-
终止状态3
-
直接终止遍历，返回得到的结果。
因此，可以得到状态转移函数：
|
空格 |
符号位 |
数字 |
其他 |
||
|
0 |
初始start |
0 |
1 |
2 |
3 |
|
1 |
符号sign |
3 |
3 |
2 |
3 |
|
2 |
数字num |
3 |
3 |
2 |
3 |
|
3 |
终止end |
有了状态转移函数，我们就可以很轻松的写出解答过程：
下面是使用Python的解答：
class Solution:
def myAtoi(self, s: str) -> int:
"""使用DFA方法实现atoi"""
sign_dist = {'+':1, '-':-1} # 符号标识种子
num_seed = '0123456789' # 数字字符种子
sign = 1 # 符号标识，1为正，-1为负
status = 0 # 初始状态为0
# 0-初始start 1-符号sign 2-数字num 3-终止end
integer = 0 # 最终要返回的整数
# 遍历字符串s
for c in s:
# 0-初始状态start
if status == 0:
if c == ' ':
continue
elif c == '+' or c == '-':
sign = sign_dist[c]
status = 1
elif c in num_seed:
integer = 10*integer + int(c)
status = 2
else:
status = 3
# 1-符号状态sign
elif status == 1:
if c == ' ' or c == '+' or c == '-':
status = 3
elif c in num_seed:
integer = 10*integer + int(c)
status = 2
else:
status = 3
# 2-数字状态num
elif status == 2:
if c == ' ' or c == '+' or c == '-':
status = 3
elif c in num_seed:
integer = 10*integer + int(c)
# 判断是否越界，越界直接返回边界值
if integer * sign < -1 * 2**31:
return -1 * 2**31
elif integer * sign > 2**31 - 1:
return 2**31 - 1
else:
status = 3
# 3-终止状态end
elif status == 3:
break
# 返回最终结果
return integer * sign
下面是使用C++的解答过程：
class Solution {
public:
int myAtoi(string s) {
// 使用DFA实现atoi
string sign_seed = "+-"; // 符号标识种子
int sign = 1; // 符号标识
int status = 0; // 初始状态为0
// 0-初始start 1-符号sign 2-数字num 3-终止end
long long integer = 0;// 最终要返回的整数
// 遍历字符串s
for(int i = 0; i < s.size(); i++){
// 通过switch进入不同的状态
switch(status){
// 0-初始状态start
case 0:
if(s[i] == ' '){
break;
}
else if(s[i] == sign_seed[0]){
sign = 1;
status = 1;
}
else if(s[i] == sign_seed[1]){
sign = -1;
status = 1;
}
else if(s[i] >= '0' && s[i] <= '9'){
integer = 10 * integer + (s[i] - '0');
status = 2;
}
else{
status = 3;
}
break;
// 1-符号状态sign
case 1:
if(s[i] == ' '){
status = 3;
}
else if(s[i] == sign_seed[0] || s[i] == sign_seed[1]){
status = 3;
}
else if(s[i] >= '0' && s[i] <= '9'){
integer = 10 * integer + (s[i] - '0');
status = 2;
}
else{
status = 3;
}
break;
// 2-数字状态num
case 2:
if(s[i] == ' '){
status = 3;
}
else if(s[i] == sign_seed[0] || s[i] == sign_seed[1]){
status = 3;
}
else if(s[i] >= '0' && s[i] <= '9'){
integer = 10 * integer + (s[i] - '0');
// 判断是否越界，越界直接返回边界值
if(integer * sign > 2147483647){
return 2147483647;
}
else if(integer * sign < -2147483648){
return -2147483648;
}
}
else{
status = 3;
}
break;
// 3-终止状态end
case 3:
break;
}
if(status == 3){
break;
}
}
return integer * sign;
}
};