有限状态机在 JavaScript 中的简单应用

Published: 2017-08-01 00:44:48

这篇文章介绍一下有限状态机以及用 js 实现一个简单的有限状态机。

首先来看看有限状态机的解释：

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

简单来说，有限状态机有三个特征：

总的状态数是有限的。
在任意时刻，只能存在于一种状态中。
满足某些条件时，可以从一种状态跳转到另外一种状态。

个人认为，有限状态机本质上就是把复杂的逻辑分解成多个（有限）稳定的状态，在每个不同状态上做相应的逻辑处理。有限状态机所具有的状态虽然说是有限的，但是并不意味着只能进行有限次的处理，反而由于有限状态机是闭环系统，其实是可以用有限的状态去处理无穷的事务的。

下面我们来看 js 中应用有限状态机的一个简单例子。

假定我们有文件 fsm.txt，这个文件中的内容如下（仅存在小写字母、数字以及换行）：

asdassaads123a567asdasdasds999s543dd
sadsasa984bdsd291hbbh786v466dsdsdssd

我们要从这个文件内容中找到符合如下格式的字符串，格式为：

左边有三个数字
中间是字母
右边是三个数字

我们很容易想到这个问题需要用到 栈 这种数据结构，单个字符扫描文件然后让符合条件的字符入栈，然后根据栈里面所代表的状态做相应的处理，具体情况如下：

初始状态: INIT，如果当前字符是数字，那么 STATE1 入栈
栈中已经有一个有效数据即已经有一个数字，此时再遇到数字时: STATE2 入栈
栈中已经有两个有效数据即已经有两个数字，此时再遇到数字时: STATE3 入栈
栈中已经有三个有效数据即已经有三个数字，此时遇到非数字时: STATE4 入栈
栈中有四个有效数据（即当前字符是数字且当前字符前面由近到远分别是一个字母三个数字）: STATE5 入栈
栈中有五个有效数据（即当前字符是数字且当前字符前面由近到远分别是一个数字一个字母三个数字）: STATE6 入栈
栈中有六个有效数据（即当前字符是数字且当前字符前面由近到远分别是两个数字一个字母三个数字）: STATE7 入栈
栈中有七个有效数据，已经满足我们的需求了，这个时候需要把数据存起来~

详细代码如下：

import {readFileSync} from 'fs';
import {join} from 'path';

/**
 * 一个简单的栈
 */
class Stack {
    /**
     * constructor
     * 初始化 Stack 实例时，每个实例默认推入一个默认的初始状态 INIT
     */
    constructor() {
        this.data = ['INIT'];
        this._data = [...this.data];
    }

    /**
     * 入栈
     *
     * @param {*} elem 入栈元素
     *
     * @return {Object} 当前 Stack 实例
     */
    push(elem) {
        this.data.push(elem);
        return this;
    }

    /**
     * 获取当前栈顶元素
     *
     * @return {*} 当前栈顶元素
     */
    peek() {
        return this.data[this.data.length - 1];
    }

    /**
     * 重置当前 Stack 实例
     *
     * @return {Object} 当前 Stack 实例
     */
    reset() {
        this.data = [...this._data];
        return this;
    }
}

/**
 * 打平数组
 *
 * @param {Array} arr 待打平数组
 *
 * @return {Array} 打平后的数组
 */
const flatten = arr => arr.reduce((pre, val) => pre.concat(Array.isArray(val) ? flatten(val.concat(' ')) : val), []);

/**
 * start
 */
const start = () => {
    const content = readFileSync(join(__dirname, '../fsm.txt'), {
        encoding: 'utf8'
    });

    const state = new Stack();

    let ret = [];
    let tmp = [];

    const len = content.length;
    let pos = 0;

    while (pos < len) {
        let char = content[pos];

        pos++;

        // 忽略换行符、回车符、换页符
        if (char === '\n' || char === '\r' || char === '\f') {
            continue;
        }

        const isNumber = !isNaN(char);

        switch (state.peek()) {
            // 初始状态: INIT，如果当前字符是数字，那么 STATE1 入栈
            case 'INIT':
                if (isNumber) {
                    state.push('STATE1');
                    tmp.push(char);
                }
                break;

            // 栈中已经有一个有效数据即已经有一个数字，此时再遇到数字时: STATE2 入栈
            case 'STATE1':
                if (isNumber) {
                    state.push('STATE2');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;

            // 栈中已经有两个有效数据即已经有两个数字，此时再遇到数字时: STATE3 入栈
            case 'STATE2':
                if (isNumber) {
                    state.push('STATE3');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;

            // 栈中已经有三个有效数据即已经有三个数字，此时遇到非数字时: STATE4 入栈
            case 'STATE3':
                if (!isNumber) {
                    state.push('STATE4');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;

            // 栈中有四个有效数据（即当前字符是数字且当前字符前面由近到远分别是一个字母三个数字）: STATE5 入栈
            case 'STATE4':
                if (isNumber) {
                    state.push('STATE5');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;

            // 栈中有五个有效数据（即当前字符是数字且当前字符前面由近到远分别是一个数字一个字母三个数字）: STATE6 入栈
            case 'STATE5':
                if (isNumber) {
                    state.push('STATE6');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;

            // 栈中有六个有效数据（即当前字符是数字且当前字符前面由近到远分别是两个数字一个字母三个数字）: STATE7 入栈 
            case 'STATE6':
                if (isNumber) {
                    state.push('STATE7');
                    tmp.push(char);
                }
                else {
                    state.reset();
                    tmp = [];
                }
                break;
            // 栈中有七个有效数据，已经满足我们的需求了，这个时候需要把数据存起来~
            case 'STATE7':
                state.reset();
                ret.push(tmp);
                tmp = [];
                break;
            default:
                break;
        }
    }

    console.log(`结果为: ${flatten(ret).join('')}`);
};

start();

参考

维基百科-有限状态机

JavaScript与有限状态机

ielgnaw

article, code and some projects

有限状态机在 JavaScript 中的简单应用

参考