数据结构和算法在前端领域的应用 — 状态机

什么是状态机

状态机表示若干个状态以及在这些状态之间的转移和动作等行为的数学模型。 通俗的描述状态机就是定义了一套状态変更的流程：状态机包含一个状态集合， 定义当状态机处于某一个状态的时候它所能接收的事件以及可执行的行为，执行完成后，状态机所处的状态。

我们以现实中广泛使用的有限状态机（以下简称 FSM）为例进行讲解

FSM 应用非常广泛， 比如正则表达式的引擎，编译器的词法和语法分析，网络协议，企业应用等很多领域都会用到。

其中正则中使用的是一种特殊的 FSM， 叫 DFA（Deterministic Finite Automaton）， 通过分裂树形式来运行。

为什么要使用状态机

第一个原因，也是大家感触最深的一个原因就是通过状态机去控制系统内部的状态以及状态流转，逻辑会 比较清晰，尤其在逻辑比较复杂的时候，这种作用越发明显。

第二个原因是通过状态机，我们可以实现数据以及系统的可视化。刚才我提到了正则表达式用到了状态机， 那么正则是否可以可视化呢？ 答案是肯定的，这里我介绍一个可视化正则表达式的一个网站。

image.png

实际业务中如果使用状态机来设计系统也可以进行可视化。类似这样子：

image.png

(图来自 statecharts.github.io/xstate-viz/)

可以看出，逻辑流转非常清晰，我们甚至可以基于此进行调试。 当然，将它作为文档的一部分也是极好的，关于状态机的实际意义还有很多，我们接下来举几个例子说明。

状态机的实际应用场景

匹配三的倍数

实现一个功能，判断一个数字是否是三的倍数。 数字可以非常大，以至于超过 Number 的表示范围， 因此我们需要用 string 来存储。

一个简单直观的做法是直接将每一位都加起来，然后看加起来的数字是否是三的倍数。 但是如果数字大到一定程度，导致加起来的数字也超过了 Number 的表示范围呢？

一个方法是使用状态机来解决。

我们发现一个数字除以 3 的余数一共有三种状态，即 0，1，2。 基于此我们可以构建一个 FSM。 0，1，2 之间的状态流转也不难得出。

举个例子，假设当前我们是余数为 0 的状态，这时候再来一个字符。

• 如果这个字符是 0,3 或者 9，那么我们的余数还是 0
• 如果这个字符是 1,4 或者 7，那么我们的余数是 1
• 如果这个字符是 2,5 或者 8，那么我们的余数还是 2

用图大概是这个样子：

image.png

<figcaption></figcaption>

如果用代码大概是这样的：

function createFSM() {
  return {
    initial: 0,
    states: {
      0: {
        on: {
          read(ch) {
            return {
              0: 0,
              3: 0,
              9: 0,
              1: 1,
              4: 1,
              7: 1,
              2: 2,
              5: 2,
              8: 2
            }[ch];
          }
        }
      },
      1: {
        on: {
          read(ch) {
            return {
              0: 1,
              3: 1,
              9: 1,
              1: 2,
              4: 2,
              7: 2,
              2: 0,
              5: 0,
              8: 0
            }[ch];
          }
        }
      },
      2: {
        on: {
          read(ch) {
            return {
              0: 2,
              3: 2,
              9: 2,
              1: 0,
              4: 0,
              7: 0,
              2: 1,
              5: 1,
              8: 1
            }[ch];
          }
        }
      }
    }
  };
}

const fsm = createFSM();
const str = "281902812894839483047309573843389230298329038293829329";
let cur = fsm.initial;

for (let i = 0; i < str.length; i++) {
  if (!["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"].includes(str[i])) {
    throw new Error("非法数字");
  }
  cur = fsm.states[cur].on.read(str[i]);
}
if (cur === 0) {
  console.log("可以被3整除");
} else {
  console.log("不可以被3整除");
}

其实代码还可以简化，读者可以下去尝试一下。

可以看出，我们这种方式逻辑清晰，且内存占用很少，不会出现溢出的情况。

正则是基于自动机实现的，那么使用正则匹配会是怎么样的呢？大家可以自己试一下。