有限状态机小结

Table of Contents

前一阵子自己留了个坑，时间长就忘了。最近看《Rust权威指南》这本书，正好碰巧又遇到了这个坑，所以今天来填下。

这个坑就是有限状态机。

《Rust权威指南》中的example #

fn main() {
    let mut post = Post::new();
    post.add_text("hello");
    let mut post = post.request_review();
    let mut post = post.approve();
    print!("{}", post.content());
}

pub struct DraftPost {
    content: String,
}

impl DraftPost {
    pub fn add_text(&mut self, text: &str) {
        self.content.push_str(text);
    }

    pub fn request_review(self) -> PendingReviewPost {
        PendingReviewPost {
            content: self.content,
        }
    }
}

pub struct PendingReviewPost {
    content: String,
}

impl PendingReviewPost {
    pub fn approve(self) -> Post {
        Post {
            content: self.content,
        }
    }
}

pub struct Post {
    content: String,
}

impl Post {
    pub fn new() -> DraftPost {
        DraftPost {
            content: String::new(),
        }
    }

    pub fn content(&self) -> &str {
        &self.content
    }
}

这是关于发布文章的流程描述。流程为：

编写草稿
发起审批
审批通过

作者将流程抽象为三个状态：

草稿状态
发起审批后的审批状态
审批通过后的已发布状态

我们说使用有限状态机能够使代码更整洁，其本质原因是因为我们将代码的复杂度拆分到了各个状态，这使得开发者在阅读或者开发时，只需要关心当前状态的逻辑。

复杂度并没有减少，只是转移了！

《游戏编程模式》里的example #

先看下作者在第七章给出的状态机：

如果不用状态机的话代码会很麻烦，需要通过大量的if/else来限制、判断动作：比如跳的时候不能再跳也不能蹲下，蹲下的时候只能站立不能进行其他动作等待。

这个状态机翻译为go语言为(只实现了下蹲状态和站立状态)：

package main

import "fmt"

// 状态接口
type HeroineState interface {
	enter(heroine *Heroine) // 进入状态
	update(heroine *Heroine) // 每秒更新一帧
	handleInput(heroine *Heroine, input string) HeroineState // 处理输入，更新状态
}

type Heroine struct {
	graphics string
	state    HeroineState
}

func (h *Heroine) setGraphics(graphics string) {
	h.graphics = graphics
}

func (*Heroine) superBomb() {
	fmt.Println("super bomb!")
}

func (h *Heroine) handleInput(input string) {
	newState := h.state.handleInput(h, input)
	h.state = newState
}

func (h *Heroine) update() {
	h.state.update(h)
}

// 蹲状态
type DuckingState struct {
	chargeTime int
}

func (ds *DuckingState) enter(heroine *Heroine) {
	heroine.setGraphics("image of ducking")
}

func (ds *DuckingState) handleInput(heroine *Heroine, input string) HeroineState {
	if input == "down" { // 蹲状态再次按“蹲”，则进入站立
		return new(StandState)
	}
	return ds
}

func (ds *DuckingState) update(heroine *Heroine) {
	ds.chargeTime++
	if ds.chargeTime > 10 { // 蓄力攻击
		heroine.superBomb()
	}
}

// 站立状态
type StandState struct{}

func (ss *StandState) enter(heroine *Heroine) {
	heroine.setGraphics("image of stand")
}

func (ss *StandState) handleInput(heroine *Heroine, input string) HeroineState {
	if input == "down" { // 蹲状态再次按“蹲”，则进入站立
		return new(DuckingState)
	}
	if input == "jump" {
		return new(JumpState)
	}
	return ss
}

func (ds *StandState) update(heroine *Heroine) {}

// 跳跃状态
type JumpState struct{}

func (js *JumpState) enter(heroine *Heroine) {
	heroine.setGraphics("image of jump")
}

func (js *JumpState) handleInput(heroine *Heroine, input string) HeroineState {
	panic("todo")
}

func (js *JumpState) update(heroine *Heroine) {}

通过将每个状态相关的所有的数据和行为封装到相关类里面降低了整体代码的复杂度

《游戏编程模式》中还介绍了“并发状态机”，“层次状态机”和“下推状态机”，有兴趣的可以去看下

实现正则匹配 #

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/regular-expression-matching

以模式串a.b*c举例，其状态机是这样的:

状态流转是根据字符进行的。
状态为匹配字符前后的索引，比如匹配第一个字符a前的状态就是0，匹配a后的状态就是1。
对于b*来说，匹配前状态为2，可以通过b来达到状态3，也可以通过不匹配（规定为None）来达到3。
同样用b*举例，达到状态3之后，再次匹配b仍会达到状态3。

python实现：

class Solution:
    def __init__(self):
        self.transfer = {} # 定义状态转移字典

    def isMatch(self, s: str, p: str) -> bool:
        state = 0 # 起始状态为0
        for i, char in enumerate(p):
            if char == '*': 
                self.append_state((state, p[i-1]), state) # 为*时，(当前状态+上个字符)还是当前状态
                self.append_state((state-1, None), state) # 为*时，(上个状态+None)转移到下个状态
            else:
                self.append_state((state, char), state+1) # 普通字符直接转移到下个状态
                state += 1

        accept = state # accept：最终状态
        states = {0} # 当前状态的集合，最一开始只有0
        for i, char in enumerate(s): 
            # 处理每个状态，并根据当前char来获取下一个有效的状态的集合
            new_state = set()
            for state in states:
                new_state |=self.process_state(state, char) 
            states = new_state
        # 对最终的状态，还要处理可能由None得到的状态
        states = self.process_final_nones(states)
        return accept in states # 所需状态是否存在于最终的状态集中

    def append_state(self, item, state):
        states = self.transfer.get(item, set())
        states.add(state)
        self.transfer[item] = states

    def process_state(self, state: int, char: str) -> set:
        new_states = set()
        for symbol in [char, '.']:
            new_states |= self.transfer.get((state, symbol), set())
        for next_state in self.transfer.get((state, None), set()):
            new_states |= self.process_state(next_state, char)
        return new_states
    
    def process_final_nones(self, states: set) -> set:
        rst = set()
        for state in states:
            rst |= self.process_final_none(state)
        return rst | states
    
    def process_final_none(self, state: int) -> set:
        states = set()
        none_states = self.transfer.get((state, None), set())
        for state in none_states:
            states |= self.process_final_none(state)
        return states | none_states

小结 #

构成 #

状态机大概由以下几个元素组成：

输入：如游戏中用户输入的指令、正则中要匹配的字符串、发表博客过程中的行为
输出：对输入所做的反应，如游戏中的人物状态改变、正则匹配结果、博客状态的变化
状态：抽象出来的事件或者属性，如游戏中的站立、下蹲，正则中的模式串的“匹配进度”，博客中的类型
状态转移：状态之间的转换逻辑

优点 #

简单清晰：有限状态机能够将问题抽象为状态和转移，从而简化了问题的表达和理解。状态机的每个状态都对应了系统的某种状态，而转移规则则描述了系统在不同状态下的行为。这种简单直观的表达方式，可以帮助我们更好地理解和设计系统。
易于扩展：通过添加新的状态和转移规则，我们可以轻松地扩展和修改有限状态机。这让我们可以逐步完善和优化系统功能，而不必重新设计整个系统。
**易于维护：通过将系统分解为多个状态和转移规则，我们可以更好地组织和管理系统代码。**状态机的每个状态都是独立的、易于测试的模块，这让我们可以更快地定位和修复错误。