有限状态机

有限状态机，刷题了解到这个概念时，惊叹了我。故此想要记录一下。

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”、”-1E-16”及”12e+5.4”都不是。

看到这样的题目，给人感觉就是好像思路了解了，但会有好多情况要判断啊。

我能尝试写出的代码是这样子的

fun check(s:String){
    // 是否是第一个字符
    var first = true
    // 第一个字符时什么了，根据该类型继续判断后面的的输入是否正确
    // 1 正负号 2 小数点 3 数字 
    var firstCharType = 0;
    for(ch in s){
        if(first){  //若是第一个字符
            first = false
            when(ch){   //记录第一个字符类型，为后续判断做为条件
                '+' or '-' ->{  
                    firstCharType = 1
                }
                in '0'..'9' ->{
                    firstCharType = 3
                }
                '.' ->{
                    firstCharType = 2
                }
                else ->{
                    return false    //第一个字符就可以确定不是数子
                }       
            }
        }else{
            when(firstCharType){    // 依据前面的状态，判断后续能有什么输入
               ...
            }
        }
    }
}

这样代码，写出来是不放心的，总感觉自己会遗漏某个分支情况。而且写出来后，代码肯定很长很繁琐。

而大佬使用有限状态机的代码是这样的。

class Solution:
    def isNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in ".eE ": t = c     # dot, e, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)

这样的代码看得真的舒服，加上配的状态转移图，逻辑也是清晰很多。大佬的题解

个人的蹩脚的理解

在一个系统中，当前的状态称为现态，外界输入称为动作, 随着输入后当前状态改变的结果称为次态, 次态生成之后便成为新的现态，周而复始。而次态的生成，不仅依赖输入，也依赖现态。这样会有这么一个逻辑，

1	state = f(state, action)

而这个函数f 是什么呢？我们可以体会到，它像数学中的条件函数，可以枚举出所有的条件，以及可接受的所有action, 结果也就随之确定。

在这道题中,比如当前状态是，前面是空格（初始状态），下一个字符只能是数字，正负号等等，而不能接受e等输入。在这道题目中，我们可以体会到状态区分不是很清晰的，当前状态时之前所有输入的叠加。

代码上，我们用states集合定义所有状态，而其中状态能够接受什么action和转移后的次态，分别用Key-Value表示。

联想日常开发中的相似的东西，当前页面的加载数据的状态。

Init –(request fetch data)–> Loading –(load failed)–> Failed –(retry)–> Loading –(load success)–> Success

这么一个流程，初始页面，请求数据，加载中，加载失败，重试，加载成功。

我们似乎可以意识到，想要达到加载成功状态，那么之前的状态是确定的，不存在从初始状态直接跳转到加载成功，期间必须经历状态加载中。在页面的加载中，似乎可以列举出所有的状态，甚至所有的函数f,状态转移的关系。

页面加载中，状态较少，输入也少，因而不引入有限状态的概念我们也能理清他们的转移关系。不过，感觉这个概念确实是个好工具，针对多个状态的场景就很有必要了。但愿以后在业务复杂的场景能够引入这个概念来解决问题。