关于状态机的思考

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

LeetCode 上有这样一道题目：表示数值的字符串。题目看似简单，但其最佳解法却蕴含着一种绝妙的工程实践——状态机。

本文从这道编程题目出发，思考了一些状态机的使用场景，记录下脑暴过程。

题目描述如下：

什么是状态机

状态机的全称为有限状态自动机（Finite-State Machine，FSM）。状态机由『状态』和『动作』两部分组成，一个状态经过某个动作之后可以转移到下一个状态。

例如，一扇门可以通过状态机来描述。

门的状态包括：

  • 开/open
  • 闭/closed

可以施加的动作包括：

  • 推/push
  • 拉/pull

状态机的表示

由上面的描述可以知道，状态机本质上等效于一个有向图（可以有环）：

  • 状态 <–> 图的顶点
  • 动作 <–> 图的边

众所周知，图有多种表示方式，除了画图外，还有邻接表、邻接矩阵等。

上例中的状态机以邻接表的形式表示如下：

1
2
3
4
5
6
7
8
9
10
{
    "open": {
        "pull": "open",
        "push": "closed"
    },
    "closed": {
        "pull": "open",
        "push": "closed"
    }
}

以邻接矩阵的形式表示如下：

PS：这只是个特例，状态图一般是非常稀疏的。

状态机怎么用

以上述 LeetCode 问题的解答为例逐步引出状态机的妙用。

PS：以下解答摘自官方题解和评论区。

解法 1. 暴力穷举

思路是通过 if...else 逻辑穷举所有可能的情况：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
class Solution {
public:

    bool is_digit(char a) { //判断是否为数字return a >= '0' && a <= '9';
    }
    bool is_e(char a) {
        return a == 'e' || a == 'E';
    }
    bool check(string st) {
        int count = 0;
        for (char i : st) {
            if (i == '.') count++;
            if (count > 1) return false;
        }
        return true;
    }
    bool isNumber(string s) {
        if (check(s) == false) return false;//确保最多只有一个小数点//前后去空格
        int i = 0;
        while (i < s.size() && s[i] == ' ') {
            i++;
        }
        int end = s.size() - 1;
        while (end >= 0 && s[end] == ' ') {
            s.erase(s.begin() + end);
            end--;
        }
        int len = s.size();
        if (s[i] == '+' || s[i] == '-') {
            i++;
            if (i >= len) return false;
            if (s[i] == '.') {
                i++;
                if (i >= len) return false;
                if (is_digit(s[i])) {
                    while (i < len && is_digit(s[i])) { i++; }
                    if (i >= len) return true;
                    if (is_e(s[i])) {
                        i++;
                        if (i >= len) return false;
                        if (s[i] == '-' || s[i] == '+') i++;
                        if (i >= len) return false;
                        while (i < len && is_digit(s[i])) { i++; }
                        if (i >= len) return true;
                        else return false;
                    }
                    else {
                        return false;
                    }
                }
                else {
                    return false;
                }
            }
            else if (is_digit(s[i])) {
                while (i < len && is_digit(s[i])) { i++; }
                if (i >= len)return true;
                if (is_e(s[i])) {
                    i++;
                    if (i >= len) return false;
                    if (s[i] == '-' || s[i] == '+') i++;
                    if (i >= len) return false;
                    while (i < len && is_digit(s[i])) { i++; }
                    if (i >= len) return true;
                    else return false;
                }
                else if (s[i] == '.' ) {
                    i++;
                    if (i >= len) return true;
                    if (is_digit(s[i])) {
                        while (i < len && is_digit(s[i])) { i++; }
                        if (i >= len) return true;
                        if (is_e(s[i])) {
                            i++;
                            if (i >= len) return false;
                            if (s[i] == '-' || s[i] == '+') i++;
                            if (i >= len) return false;
                            while (i < len && is_digit(s[i])) { i++; }
                            if (i >= len) return true;
                            else return false;
                        }
                        else {
                            return false;
                        }
                    }
                    else if (is_e(s[i])) {
                        i++;
                        if (i >= len) return false;
                        if (s[i] == '-' || s[i] == '+') i++;
                        if (i >= len) return false;
                        while (i < len && is_digit(s[i])) { i++; }
                        if (i >= len) return true;
                        else return false;
                    }
                    else {
                        return false;
                    }
                }
                else {
                    return false;
                }
            }
            else {
                return false;
            }
        }
        else if (s[i] == '.') {
            i++;
            if (i >= len) return false;
            if (is_digit(s[i])) {
                while (i < len && is_digit(s[i])) { i++; }
                if (i >= len) return true;
                if (is_e(s[i])) {
                    i++;
                    if (i >= len) return false;
                    if (s[i] == '-' || s[i] == '+') i++;
                    if (i >= len) return false;
                    while (i < len && is_digit(s[i])) { i++; }
                    if (i >= len) return true;
                    else return false;
                }
                else {
                    return false;
                }
            }
        }
        else if (is_digit(s[i])) {
            while (i < len && is_digit(s[i])) { i++; }
            if (i >= len) return true;
            if (s[i] == '.') {
                i++;
                if (i >= len) return true;
                if (is_digit(s[i])) {
                    while (i < len && is_digit(s[i])) { i++; }
                    if (i >= len) return true;
                    else if (is_e(s[i])) {
                        i++;
                        if (i >= len) return false;
                        if (s[i] == '-' || s[i] == '+') i++;
                        if (i >= len) return false;
                        while (i < len && is_digit(s[i])) { i++; }
                        if (i >= len) return true;
                        else return false;
                    }
                    else {
                        return false;
                    }
                }
                else if (is_e(s[i])) {
                    i++;
                    if (i >= len) return false;
                    if (s[i] == '-' || s[i] == '+') i++;
                    if (i >= len) return false;
                    while (i < len && is_digit(s[i])) { i++; }
                    if (i >= len) return true;
                    else return false;
                }
                else {
                    return false;
                }
            }
            else if (is_e(s[i])) {
                i++;
                if (i >= len) return false;
                if (s[i] == '-' || s[i] == '+') i++;
                if (i >= len) return false;
                while (i < len && is_digit(s[i])) { i++; }
                if (i >= len) return true;
                else return false;
            }
            else {
                return false;
            }
        }
        else {
            return false;
        }
        return false;
    }
};

不足：

  • 冗长，可读性差
  • 难以确认代码逻辑的正确性

解法 2. 状态编程

比起暴力穷举，通过声明一些全局变量来保存状态，可复用一部分代码逻辑。

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
class Solution {
public:
    bool isNumber(string s) {
        if(s.size() == 0) return false;

        //跳过首尾空格int left = 0, right = s.length() - 1;
        while(left <= right && s[left] == ' '){
            left++;
        }
        if(left > right) return false;
        while(left < right && s[right] == ' '){
            right--;
        }

        bool isNum = false;
        bool isDot = false;
        bool isEe = false;
        bool isSign = false;

        for(int i = left; i <= right; i++){
            if(s[i] >= '0' && s[i] <= '9'){
                isNum = true;
            }
            // 一个'.'；e/E后面跟一个整数（不能有'.'）
            else if(s[i] == '.' && !isDot && !isEe){
                isDot = true;
            }
            // 一个'E'或'e'；前面需要出现过数字
            else if((s[i] == 'E' || s[i] == 'e') && isNum && !isEe){
                isEe = true;
                //// 避免e结尾的情况 e后面得跟一个整数
                isNum = false;
            }
            // '+''-'只能出现在开头或者'E'或'e'的后一位
            else if((s[i] == '+' || s[i] == '-') && (i == left || s[i - 1] == 'E' || s[i - 1] == 'e')){
                isSign = true;
            }
            else{
                return false;
            }
        }
        // 必须以数字结尾
        return isNum;
    }
};

不足：

  • 状态变量多，不容易读懂
  • 难以确认代码逻辑的正确性

解法 3. 状态机

在解法 2 的基础上进一步抽象，整理出各种状态以及可能遇到的字符的类型。

可以发现状态和类型都是有限的，并且它们之间的转移关系是确定的。如下图：

邻接矩阵：

邻接表：

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
{
    "state_initial": {
        "char_space": "state_initial",
        "char_number": "state_integer",
        "char_point": "state_point_without_int",
        "char_sign": "state_int_sign"
    },
    "state_int_sign": {
        "char_number": "state_integer",
        "char_point": "state_point_without_int"
    },
    "state_integer": {
        "char_number": "state_integer",
        "char_exp": "state_exp",
        "char_point": "state_point",
        "char_space": "state_end"
    },
    "state_point": {
        "char_number": "state_fraction",
        "char_exp": "state_exp",
        "char_space": "state_end"
    },
    "state_point_without_int": {
        "char_number": "state_fraction"
    },
    "state_fraction": {
        "char_number": "state_fraction",
        "char_exp": "state_exp",
        "char_space": "state_end"
    },
    "state_exp": {
        "char_number": "state_exp_number",
        "char_sign": "state_exp_sign"
    },
    "state_exp_sign": {
        "char_number": "state_exp_number"
    },
    "state_exp_number": {
        "char_number": "state_exp_number",
        "char_space": "state_end"
    },
    "state_end": {
        "char_space": "state_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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
from enum import Enum

class Solution:
    def isNumber(self, s: str) -> bool:
        # 定义所有状态
        State = Enum("State", [
            "STATE_INITIAL",
            "STATE_INT_SIGN",
            "STATE_INTEGER",
            "STATE_POINT",
            "STATE_POINT_WITHOUT_INT",
            "STATE_FRACTION",
            "STATE_EXP",
            "STATE_EXP_SIGN",
            "STATE_EXP_NUMBER",
            "STATE_END"
        ])
        # 定义所有动作
        Chartype = Enum("Chartype", [
            "CHAR_NUMBER",
            "CHAR_EXP",
            "CHAR_POINT",
            "CHAR_SIGN",
            "CHAR_SPACE",
            "CHAR_ILLEGAL"
        ])

        def toChartype(ch: str) -> Chartype:
            if ch.isdigit():
                return Chartype.CHAR_NUMBER
            elif ch.lower() == "e":
                return Chartype.CHAR_EXP
            elif ch == ".":
                return Chartype.CHAR_POINT
            elif ch == "+" or ch == "-":
                return Chartype.CHAR_SIGN
            elif ch == " ":
                return Chartype.CHAR_SPACE
            else:
                return Chartype.CHAR_ILLEGAL

        # 定义状态机：邻接表表示法
        transfer = {
            State.STATE_INITIAL: {
                Chartype.CHAR_SPACE: State.STATE_INITIAL,
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
                Chartype.CHAR_SIGN: State.STATE_INT_SIGN
            },
            State.STATE_INT_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
            },
            State.STATE_INTEGER: {
                Chartype.CHAR_NUMBER: State.STATE_INTEGER,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_POINT: State.STATE_POINT,
                Chartype.CHAR_SPACE: State.STATE_END
            },
            State.STATE_POINT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_SPACE: State.STATE_END
            },
            State.STATE_POINT_WITHOUT_INT: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION
            },
            State.STATE_FRACTION: {
                Chartype.CHAR_NUMBER: State.STATE_FRACTION,
                Chartype.CHAR_EXP: State.STATE_EXP,
                Chartype.CHAR_SPACE: State.STATE_END
            },
            State.STATE_EXP: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
            },
            State.STATE_EXP_SIGN: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
            },
            State.STATE_EXP_NUMBER: {
                Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
                Chartype.CHAR_SPACE: State.STATE_END
            },
            State.STATE_END: {
                Chartype.CHAR_SPACE: State.STATE_END
            },
        }

        # 程序主体
        st = State.STATE_INITIAL         # 进入初始状态
        for ch in s:                     # 遍历动作
            typ = toChartype(ch)
            if typ not in transfer[st]:  # 如果动作无法使状态流转，则宣告失败
                return False
            st = transfer[st][typ]       # 流转到下一个状态

        # 判断是否到达完成状态
        return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]

优势：

  • 状态表的含义一目了然，含义清晰
  • 可以遍历状态转移关系确认代码的正确性
  • 代码量少，逻辑简单

为什么要使用状态机

状态机不是一个良好的算法，而是一个优秀的工程实践！ 因为状态机本质上还是穷举，既没有降低时间复杂度，也没有降低空间复杂度。

使用状态机的好处：

  • 强制理清思路，不容易出错。
  • 方便修改和扩展。尤其是在工程上线后，不需要修改代码，调整邻接表配置即可。
  • 高度抽象。将繁琐的 if...else 逻辑抽象成一套公共库，节约开发成本。在 Java、Python 等热门语言中都有大量的状态机库可供调用。

状态机的应用

有『状态』和『变化』的地方就可以有状态机。

  • 编译器/解释器
    • 如何识别语法错误？例如括号不闭合、int a = /2。
  • 正则表达式
    • \d+ 与 1，123a match 不上，中间发生了什么？
  • 网络协议，如 TCP
    • 握手阶段在等待 ACK 的过程中不接受 SYN、不接受数据。
  • 订单系统
    • 付款、取消、等待、投诉等动作会对订单状态产生什么影响？
  • 游戏任务设计
    • 和 NPC 对话后再做某项任务与直接做某项任务效果不同。
  • 一种全面、系统的思考问题的方式，可用于做问题建模。例如：
    • Airflow 中的任务状态建模：
      • 任务 pending 状态发起重试会发生什么？
      • 任务运行中状态置成功会发生什么？
      • 对 pending 任务发起回溯会发生什么？
      • 对 pending 任务修改调度周期会发生什么？
    • 一些权限系统中的糟糕设计：
      • 自己创建的资源，默认没权限，需要自己给自己申请权限
      • 管理员可以移除任何人的权限，但把自己的权限移除了