使用有限状态机(FSM)处理字符串

时间:2021-1-8 作者:admin

前言

有限状态机是(Finite State Machine,简写 FSM),是一种可以表现事物在有限个状态以及在这些状态之间进行转移的模型。本文主要介绍如何使用有限状态机思想来处理字符串。

有限状态机有两种类型:

  • Moore 机:摩尔型状态机。下一状态取决于当前状态和当前输入,输出依赖于当前状态。
  • Mealy 机:米利型状态机。下一状态和输出依赖于于当前状态和当前输入。

查找子串实现

例 1

先来一个简单的例子:如何在一个字符串中查找 abc ?思路比较简单,代码如下:

function match (string) {
    let foundA = false
    let foundB = false

    for (let c of string) {
        if (c === 'a') {
            foundA = true
        } else if (foundA && c === 'b') {
            foundB = true
        } else if (foundB && c === 'c') {
            return true;
        } else {
            foundA = false
            foundB = false
        }
    }
    return false
}

console.log(match('abc'))   // true
console.log(match('acbc'))  // false

这里使用一个简单的思路,来实现子串 ‘abc’ 的查找。但也有一个明显的缺点就是,当查找的字符串变多时,循环中的 if-else 判断逻辑会非常臃肿。遇到类似这样的问题,我们便可以尝试使用有限状态机的方式来处理。

JavaScript 有限状态机

对于上面的字符串查找问题,我们使用 Mealy 类型状态机来处理。下面是程序的主体逻辑:

function state (input) {
    doSomething()
    return next;
}

for (let c of string) {
    state = state(c);
}
  1. state 函数代表一种状态,函数的参数就是输入。在函数体中,添加对参数(状态) 的处理逻辑,并将返回值作为下一个状态。
  2. 调用过程中,仍然是通过遍历字符实现。遍历结束后,我们通过最终的 state 的最终状态来判定子串是否查找成功。

例 2

在一个字符串中查找 NICE?

可以梳理一个状态表,有利于分析状态以及它们之间的关系。

在上表中,x 表示回到原始的 start 状态, 表示查找成功的状态。分别预设了 startfoundNfoundIfoundCsuccess 5种状态。每种状态函数中会对遇到的字符,进行状态处理,符合条件的就会迁移到下一状态。所以,当 NICE 字符串查找成功后,过程就是:start -> foundN -> foundI -> foundC -> foundE -> success

代码实现
/**
 * 查找字符串 'NICE'
 * @param {String} string 
 */
function match(string) {
    let state = start
    for (let c of string) {
        state = state(c)
    }
    return state === success
}

function start (c) {
    if (c === 'N') {
        return foundN
    } else {
        return start
    }
}

function success (c) {
    return arguments.callee
}

function foundN (c) {
    if (c === 'I') {
        return foundI
    } else {
        return start
    }
}

function foundI (c) {
    if (c === 'C') {
        return foundC
    } else {
        return start
    }
}

function foundC (c) {
    if (c === 'E') {
        return success
    } else {
        return start
    }
}

console.log(match('NIABC'))         // false
console.log(match('AB NICE KL'))    // true
console.log(match('NICNIC'))        // false

demo

完整示例代码

参考

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。