有限状态机

状态机

假设我们要解决这样一个问题，判断给定的一个字符串是否符合一个语法标准。那么输入就是一个字符串，输出是true或者false，中间的处理过程就是状态机的实现。状态机在逐个接受输入字符的过程中，其中的状态会发生改变，最终停止在某个状态，并有输出产生。可以把状态机看作是有记忆的，但其实是我们定义好的行为。

状态机大致可以分为四个元素：现态、事件、动作、次态。此时的状态机处于现态，发生事件之后，会产生动作，同时改变状态到下一个状态。

如果一个状态机的状态数目是有限的，那么就称这个状态机为有限状态机。

有限状态机（Finite State Machine）是表示有限个状态（State）以及在这些状态（State）之间的转移（Transition）和动作（Action）等行为的数据模型。

总的来说，有限状态机系统，是指在不同阶段呈现出不同的运行状态的系统，这些状态是有限的、不重叠的。

这样的系统在某一时刻一定会处于其所有状态中的一个状态，此时它接收一部分允许的输入，产生一部分可能的响应，并迁移到一部分可能的状态。

https://glumes.com/post/android/understand-state-machine/

其实对于很多的程序来说，逻辑虽然没有多复杂，但是写出来的代码却一团糟，一个主要原因就是程序背后没有一个有效的模型支持。这个时候有限状态机很有可能会派上用场。

特别有感触的是，当我们编码时会常常纠结于模块的划分，函数内容的定义。把握不好的话写出来的代码往往很难理解，而且不好维护。那么用上状态机之后，每次编码之前都会详尽的定义状态，明确地画出状态之间的转移关系，这样可以大大减少编码时的工作量，而且对于后期扩展优化都很有帮助。

valid number

leetcode 上的一道题目，给你一个字符串，判断其是否是数字。

示例，

"0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true

看似简单，如果不借助语言本身的特性，并且盲目去判断，问题会很复杂。一个有效又优雅的解法就是借助状态机。

用状态机去描述问题的关键地方就是枚举所有的状态，并且画出状态转移图，这是最花时间的地方。

下面这个解法来自 https://blog.csdn.net/kenden23/article/details/18696083

其枚举了九种状态

初始无输入或者只有space的状态
输入了数字之后的状态
前面无数字，只输入了Dot的状态
输入了符号状态
前面有数字和有dot的状态
‘e’ or ‘E’输入后的状态
输入e之后输入Sign的状态
输入e后输入数字的状态
前面有有效数输入之后，输入space的状态

并将输入分为六类：

INVALID, // 0 Include: Alphas, ‘(‘, ‘&’ ans so on
SPACE, // 1
SIGN, // 2 ‘+’,’-‘
DIGIT, // 3 numbers
DOT, // 4 ‘.’
EXPONENT, // 5 ‘e’ ‘E’

有了状态和输入事件就可以画状态转移图了，画完图就可以写程序了。

class Solution {
public:
	bool isNumber(const char *s) {
		enum InputType {
			INVALID,    // 0 Include: Alphas, '(', '&' ans so on
			SPACE,		// 1
			SIGN,		// 2 '+','-'
			DIGIT,		// 3 numbers
			DOT,			// 4 '.'
			EXPONENT,		// 5 'e' 'E'
		};
		int transTable[][6] = {
		//0INVA,1SPA,2SIG,3DI,4DO,5E
			-1,  0,  3,  1,  2, -1,//0初始无输入或者只有space的状态
			-1,  8, -1,  1,  4,  5,//1输入了数字之后的状态
			-1, -1, -1,  4, -1, -1,//2前面无数字，只输入了Dot的状态
			-1, -1, -1,  1,  2, -1,//3输入了符号状态
			-1,  8, -1,  4, -1,  5,//4前面有数字和有dot的状态
			-1, -1,  6,  7, -1, -1,//5'e' or 'E'输入后的状态
			-1, -1, -1,  7, -1, -1,//6输入e之后输入Sign的状态
			-1,  8, -1,  7, -1, -1,//7输入e后输入数字的状态
			-1,  8, -1, -1, -1, -1,//8前面有有效数输入之后，输入space的状态
		};
		int state = 0;
		while (*s)
		{
			InputType input = INVALID;
			if (*s == ' ') input = SPACE;
			else if (*s == '+' || *s == '-') input = SIGN;
			else if (isdigit(*s)) input = DIGIT;
			else if (*s == '.') input = DOT;
			else if (*s == 'e' || *s == 'E') input = EXPONENT;
			state = transTable[state][input];
			if (state == -1) return false;
			++s;
		}
		return state == 1 || state == 4 || state == 7 || state == 8;
	}
};

状态机

有限状态机

valid number

其他