leetcode 8 将字符串转换成整数atoi（有限状态机解法）中等

leetcode 8 将字符串转换成整数atoi（有限状态机解法）中等

针对本题引入自动机：

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。
因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：
我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题

代码实现：

#include
using namespace std;
#include
#include
#include


//有限状态机解法
class Automation
{
	string state = "start";  // 一共有start signed in_number end四个状态
	unordered_map>table =   //哈希表的key表示前一个状态 value表示从当前状态可以转化到的下一个状态
	{
		{"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;//为空返回0
		if (c == '+' || c == '-')return 1;//为+ - 返回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_MAX));
		}
		else if (state == "signed")
		{
			sign = (c == '+'? 1:-1);
		}
	}
};

class Solution
{
public:
	int myAtoi(string str)
	{
		Automation automation;
		for (char c : str)
		{
			automation.get(c);
		}
		return automation.sign * automation.ans;
	}
};
int main()
{
	system("pause");
	return 0;
}

---

补充关于有限状态机的知识：
有限状态机，（英语：Finite-state machine, FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

常见的计算机就是使用有限状态机作为计算模型的：
对于内存的不同状态，CPU通过读取内存值进行计算，更新内存中的状态。CPU还通过消息总线接受外部输入设备（如键盘、鼠标）的指令，计算后更改内存中的状态，计算结果输出到外部显示设备（如显示器），以及持久化存储在硬盘。
电脑游戏设计中也经常使用有限状态机模型。以水果忍者游戏为例，游戏中水果的状态是有限状态，其运行轨迹是由模拟物理运动规律的计算公式运算而成的，一个香蕉抛起来后会按照抛物线运行，其每一帧位置变化都是一个状态的改变，状态改变通过计算公式来决定。当然作为游戏不会仅仅这么简单，如果这么简单就是动画了，游戏还有复杂的人机交互事件，比如用手在屏幕上“切”了水果，水果感知到这个事件后，会按照程序逻辑进入爆炸状态。

简单知道其定义是没有用的，在C编程中我们改如何应用呢？
例题1：去除一个字符串中连续的空格，即 Ｈ＿＿ｅｌ＿＿＿ｌｏ　变成　Ｈ＿ｅｌ＿ｌｏ；
我们拿到这道题时，可能会想到用getchar()依次取字符，当遇到空格时，继续下一个字符是否为空格，如果是则删除，如果不是则继续；那么问题来了，如果空格后面还有空格呢？如果还有很多空格呢？如果还有其他要求呢？这样很容易造成思维混乱，所以这时我们可以用到有限状态机模型，好像这样说很模糊啊，该怎么使用呢？利用这种方式，最后的就是利用好flag,即标识符；这样吧，我们来画一下这个模型：

状态0 (flag = 1)若当前字符是空格，输出并跳转到状态1(flag = 1),如果是非空格，则打印字符；
状态1 (flag = 1) 若当前字符为非空格，则输出并跳转到状态0，若是空格，则不打印；

---

补充关于ASCII的知识：
字符和数字的转换：下面就说说为什么字符减’0’可以到相应的整数。
现在比如我们要字符‘1’转换成数字1，就这么一个变化，我们看到了大家注意了字符型常量用’ '括起来的原因是，它们在计算机中都以各自的ASCII表示。而‘1’的对应编码是49的二进制码，但是我们的数字1，就等于1呀，所以为了由原来的‘1’实际上就是49的二进制变成现在的1对应的二进制1，只好用49-48=1了。但是在ASCII码里‘0’对应的刚好是48的二进制码，所以我们转换的时候只需要‘1’-‘0’=1；就可以了。而数字的ASCII码是按顺序规定的。所以其它字符要转换成数字都可以用减‘0’来表示。比如‘2’的ASCII是50，而我们要得到数字2，于是用‘2’-48=2了。
大小写字母的转换：先看ASCII码：az是97122的二进制，而AZ是6590的二进制编码，于是我们就得出：大写字母=小写字母-32 ；这个公式了。当然这里的32我也可以这么写‘Z’=‘z’-‘空格’。因为空格的ASCII码是32对应的二进制编码。