C++ 有限状态自动机（FSM）：原理、实现与应用全解析

C++ 有限状态自动机（FSM）：原理、实现与应用全解析

有限状态自动机（Finite State Machine, FSM，也叫有限状态机）是一种抽象计算模型，核心思想是将复杂的逻辑拆解为「状态」和「状态转移」，通过输入触发状态变化，最终完成特定逻辑处理。它广泛应用于编译器、协议解析、文本处理、游戏 AI 等场景，也是实现 AC 自动机、KMP 等算法的底层思想。本文将从核心原理、分类、C++ 实现模式到实战案例，全面解析有限状态自动机的设计与落地技巧。

一、有限状态自动机的核心背景与定义

1.1 问题引入：复杂逻辑的结构化拆解

面对需要根据'上下文/历史输入'做决策的场景（如解析 JSON、验证手机号、处理 TCP 协议），纯分支判断（if-else/switch）会导致代码臃肿、可读性差、易出错：

// 反面例子：用 switch 验证手机号（仅 11 位数字，以 1 开头）
bool validatePhone(const string& s) {
    if (s.size() != 11) return false;
    for (int i = 0; i < s.size(); ++i) {
        switch (i) {
            case 0: if (s[i] != '1') return false; break;
            default: if (!isdigit(s[i])) return false; break;
        }
    }
    return true;
}

这种写法在规则复杂时（如支持带区号、分机号的手机号）会迅速失控。

有限状态自动机的核心价值：

• 结构化：将逻辑拆分为「状态」「输入」「转移规则」，代码可维护性大幅提升；
• 可扩展：新增规则只需添加状态/转移，无需修改核心逻辑；
• 可验证：状态机的逻辑可通过画图/数学方法验证正确性。

1.2 核心概念定义

一个有限状态自动机由 5 个核心元素组成（五元组）：

1. 状态集合（S）：所有可能的状态，包含：
   • 初始状态（Start State）：自动机的起始点；
   • 终止状态（Accept State）：表示逻辑完成/验证通过的状态；
   • 中间状态：处理输入的过渡状态。
2. 输入字母表（Σ）：所有可能的输入类型（如数字、字母、特定字符）。
3. 转移函数（δ）：δ(current_state, input) → next_state，定义'当前状态 + 输入'对应的下一个状态。
4. 初始状态（s₀）：属于 S，自动机的起点。
5. 终止状态集合（F）：F ⊆ S，代表逻辑完成的状态。

分类：

• 确定性有限状态自动机（DFA）：每个状态 + 输入对应唯一的下一个状态（实战中最常用）；
• 非确定性有限状态自动机（NFA）：每个状态 + 输入对应多个下一个状态，可通过子集构造法转为 DFA。

示例：验证'11 位手机号（以 1 开头，后 10 位为数字）'的 DFA：

• 状态集合 S：{初始态 S0, 数字态 S1, 终止态 S2, 错误态 S3}；
• 输入字母表 Σ：{数字字符（0-9）}；
• 转移函数：
  • δ(S0, '1') → S1；δ(S0, 非'1') → S3；
  • δ(S1, 数字) → S1（累计 9 次后）→ S2；δ(S1, 非数字) → S3；
  • δ(S2, 任意) → S3；δ(S3, 任意) → S3；
• 初始状态 s₀：S0；
• 终止状态 F：{S2}。

二、有限状态自动机的 C++ 实现模式

有限状态自动机的实现有多种模式，从简单到复杂依次为：表驱动型、状态对象型、函数指针/回调型，其中表驱动型是实战中最常用的方式。

2.1 模式 1：表驱动型 DFA（最简洁，适合简单逻辑）

核心思想：用二维数组/哈希表存储转移规则，通过查表实现状态转移，代码结构清晰、易扩展。

实现步骤：

1. 定义状态枚举；
2. 定义转移表（状态×输入→下一个状态）；
3. 实现输入处理逻辑，遍历输入并查表转移状态；
4. 最终判断是否处于终止状态。

完整实现（验证 11 位手机号）：

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

// 步骤 1：定义状态枚举
enum State {
    S0, // 初始状态：等待输入第一位（必须是 1）
    S1, // 中间状态：已输入 1 位，还需输入 10 位数字
    S2, // 终止状态：已输入 11 位有效手机号
    S3  // 错误状态：输入无效
};

// 步骤 2：定义输入类型（简化：仅区分'1'、其他数字、非数字）
enum InputType {
    INPUT_1,      // 字符'1'
    INPUT_DIGIT,  // 其他数字（0,2-9）
    INPUT_OTHER   // 非数字字符
};

// 辅助函数：将输入字符转为 InputType
InputType getInputType(char c) {
    if (!isdigit(c)) return INPUT_OTHER;
    if (c == '1') return INPUT_1;
    return INPUT_DIGIT;
}

int main() {
    // 步骤 3：构建转移表（二维数组：当前状态 × 输入类型 → 下一个状态）
    State transition_table[4][3] = {
        // S0 的转移：INPUT_1→S1，INPUT_DIGIT→S3，INPUT_OTHER→S3
        {S1, S3, S3},
        // S1 的转移：需累计输入 10 位数字后到 S2，否则保持 S1；非数字到 S3
        {S1, S1, S3},
        // S2 的转移：任意输入到 S3
        {S3, S3, S3},
        // S3 的转移：任意输入保持 S3
        {S3, S3, S3}
    };

    // 测试用例
    vector<string> test_cases = {"13800138000", "1234567890", "23800138000", "1380013800a"};
    for (const string& phone : test_cases) {
        State current_state = S0;
        int digit_count = 0; // 记录 S1 状态下输入的数字数

        // 步骤 4：遍历输入，执行状态转移
        for (char c : phone) {
            InputType input = getInputType(c);
            current_state = transition_table[current_state][input];

            // 处理 S1 的特殊逻辑：累计数字数到 10 则转为 S2
            if (current_state == S1) {
                digit_count++;
                if (digit_count == 10) {
                    current_state = S2;
                }
            }

            // 错误状态直接终止
            if (current_state == S3) break;
        }

        // 步骤 5：判断是否处于终止状态
        bool valid = (current_state == S2);
        cout << "手机号：" << phone << " → " << (valid ? "有效" : "无效") << endl;
    }
    return 0;
}

输出结果：

手机号：13800138000 → 有效 
手机号：1234567890 → 无效 
手机号：23800138000 → 无效 
手机号：1380013800a → 无效 

2.2 模式 2：状态对象型 DFA（面向对象，适合复杂逻辑）

核心思想：将每个状态封装为类/对象，状态转移由对象自身处理，符合开闭原则（新增状态无需修改原有代码）。

完整实现（解析简单的键值对：key=value）：

#include<iostream>
#include<string>
#include<memory>
using namespace std;

// 前向声明状态基类
class State;

// 上下文类：存储自动机的状态、输入、结果等信息
class Context {
public:
    string input;     // 输入字符串
    int pos;          // 当前处理位置
    string key;       // 解析出的 key
    string value;     // 解析出的 value
    bool is_valid;    // 是否解析成功
    shared_ptr<State> current_state; // 当前状态

    Context(const string& in) : input(in), pos(0), is_valid(false) {}

    // 切换状态
    void setState(shared_ptr<State> state) {
        current_state = state;
    }

    // 获取当前输入字符（越界返回'\0'）
    char getCurrentChar() {
        return (pos < input.size()) ? input[pos] : '\0';
    }

    // 移动到下一个字符
    void nextChar() {
        if (pos < input.size()) pos++;
    }
};

// 状态基类（抽象类）
class State {
public:
    virtual ~State() = default;
    // 处理当前输入，返回下一个状态
    virtual void handle(Context& ctx) = 0;
};

// 初始状态：等待输入 key 的第一个字符
class StartState : public State {
public:
    void handle(Context& ctx) override {
        char c = ctx.getCurrentChar();
        if (c == '\0') {
            // 空输入
            ctx.is_valid = false;
            return;
        }
        if (isalnum(c)) {
            // 字母/数字：加入 key，切换到 KeyState
            ctx.key += c;
            ctx.nextChar();
            ctx.setState(make_shared<KeyState>());
        } else {
            // 无效字符
            ctx.is_valid = false;
        }
    }
};

// Key 状态：继续输入 key，直到遇到'='
class KeyState : public State {
public:
    void handle(Context& ctx) override {
        char c = ctx.getCurrentChar();
        if (c == '=') {
            // 遇到等号：切换到 ValueState
            ctx.nextChar();
            ctx.setState(make_shared<ValueState>());
        } else if (isalnum(c)) {
            // 字母/数字：继续加入 key
            ctx.key += c;
            ctx.nextChar();
        } else {
            // 无效字符
            ctx.is_valid = false;
        }
    }
};

// Value 状态：输入 value，直到结束
class ValueState : public State {
public:
    void handle(Context& ctx) override {
        char c = ctx.getCurrentChar();
        if (c == '\0') {
            // 输入结束：验证通过
            ctx.is_valid = !ctx.value.empty();
            return;
        }
        if (isalnum(c)) {
            // 字母/数字：加入 value
            ctx.value += c;
            ctx.nextChar();
        } else {
            // 无效字符
            ctx.is_valid = false;
        }
    }
};

// 有限状态自动机类
class KeyValueParser {
private:
    Context ctx;
public:
    KeyValueParser(const string& input) : ctx(input) {
        // 初始状态为 StartState
        ctx.setState(make_shared<StartState>());
    }

    // 执行解析
    bool parse() {
        while (ctx.current_state && ctx.is_valid != false) {
            ctx.current_state->handle(ctx); // 输入处理完毕则退出
            if (ctx.getCurrentChar() == '\0') break;
        }
        return ctx.is_valid;
    }

    // 获取解析结果
    pair<string, string> getResult() {
        return {ctx.key, ctx.value};
    }
};

// 测试代码
int main() {
    vector<string> test_cases = {"name=alice", "age=20", "id=12345", "invalid=123#", "empty="};
    for (const string& s : test_cases) {
        KeyValueParser parser(s);
        bool success = parser.parse();
        auto [key, value] = parser.getResult();
        cout << "输入：" << s << " → " << (success ? "解析成功" : "解析失败");
        if (success) {
            cout << " (key=" << key << ", value=" << value << ")";
        }
        cout << endl;
    }
    return 0;
}

输出结果：

输入：name=alice → 解析成功 (key=name, value=alice)
输入：age=20 → 解析成功 (key=age, value=20)
输入：id=12345 → 解析成功 (key=id, value=12345)
输入：invalid=123# → 解析失败
输入：empty= → 解析失败

2.3 模式 3：函数指针/回调型（灵活，适合高性能场景）

核心思想：用函数指针/std::function 代替状态类，减少对象创建开销，适合高性能、简单状态机场景。

#include<iostream>
#include<string>
#include<functional>
using namespace std;

// 上下文结构体
struct FSMContext {
    string input;
    int pos;
    bool is_valid;
    // 状态转移函数类型：Context → 下一个状态函数
    using StateFunc = function<void(FSMContext&)>;
    StateFunc current_state;

    FSMContext(const string& in) : input(in), pos(0), is_valid(true) {}
};

// 状态函数：初始状态（验证是否为数字）
void state_start(FSMContext& ctx) {
    if (ctx.pos >= ctx.input.size()) {
        ctx.is_valid = false;
        return;
    }
    char c = ctx.input[ctx.pos];
    if (isdigit(c)) {
        ctx.pos++;
        ctx.current_state = [](FSMContext& ctx) { state_digit(ctx); };
    } else {
        ctx.is_valid = false;
    }
}

// 状态函数：数字状态（持续验证数字）
void state_digit(FSMContext& ctx) {
    if (ctx.pos >= ctx.input.size()) {
        // 输入结束，验证通过
        return;
    }
    char c = ctx.input[ctx.pos];
    if (isdigit(c)) {
        ctx.pos++;
    } else {
        ctx.is_valid = false;
    }
}

// 测试：验证纯数字字符串
bool validateNumber(const string& s) {
    FSMContext ctx(s);
    ctx.current_state = state_start;
    while (ctx.current_state && ctx.is_valid) {
        ctx.current_state(ctx); // 输入处理完毕则退出
        if (ctx.pos >= s.size()) break;
    }
    return ctx.is_valid;
}

int main() {
    cout << boolalpha;
    cout << validateNumber("12345") << endl; // true
    cout << validateNumber("123a5") << endl; // false
    cout << validateNumber("") << endl;      // false
    return 0;
}

三、有限状态自动机的实战应用

3.1 应用 1：文本分词（简单关键词提取）

实现一个分词器，提取文本中的'数字''字母''标点'三类 token：

enum TokenType {
    TOKEN_DIGIT,
    TOKEN_ALPHA,
    TOKEN_PUNCT,
    TOKEN_EOF
};

enum State {
    S_INIT,
    S_DIGIT,
    S_ALPHA,
    S_PUNCT
};

struct Token {
    TokenType type;
    string value;
};

vector<Token> tokenize(const string& text) {
    vector<Token> tokens;
    State current_state = S_INIT;
    string current_token;
    auto flush_token = [&](TokenType type) {
        if (!current_token.empty()) {
            tokens.push_back({type, current_token});
            current_token.clear();
        }
    };

    for (char c : text) {
        switch (current_state) {
            case S_INIT:
                if (isdigit(c)) {
                    current_token += c;
                    current_state = S_DIGIT;
                } else if (isalpha(c)) {
                    current_token += c;
                    current_state = S_ALPHA;
                } else if (ispunct(c)) {
                    current_token += c;
                    current_state = S_PUNCT;
                }
                break;
            case S_DIGIT:
                if (isdigit(c)) {
                    current_token += c;
                } else {
                    flush_token(TOKEN_DIGIT);
                    current_state = S_INIT; // 回退字符，重新处理
                    if (isalpha(c) || ispunct(c)) {
                        // 重新处理当前字符
                        current_token += c;
                        current_state = isalpha(c) ? S_ALPHA : S_PUNCT;
                    }
                }
                break;
            case S_ALPHA:
                if (isalpha(c)) {
                    current_token += c;
                } else {
                    flush_token(TOKEN_ALPHA);
                    current_state = S_INIT;
                    if (isdigit(c) || ispunct(c)) {
                        current_token += c;
                        current_state = isdigit(c) ? S_DIGIT : S_PUNCT;
                    }
                }
                break;
            case S_PUNCT:
                flush_token(TOKEN_PUNCT);
                current_state = S_INIT;
                if (isdigit(c) || isalpha(c)) {
                    current_token += c;
                    current_state = isdigit(c) ? S_DIGIT : S_ALPHA;
                }
                break;
        }
    }

    // 处理最后一个 token
    if (current_state == S_DIGIT) flush_token(TOKEN_DIGIT);
    else if (current_state == S_ALPHA) flush_token(TOKEN_ALPHA);
    else if (current_state == S_PUNCT) flush_token(TOKEN_PUNCT);
    tokens.push_back({TOKEN_EOF, ""});
    return tokens;
}

// 测试
int main() {
    string text = "hello123,world456!";
    auto tokens = tokenize(text);
    for (const auto& token : tokens) {
        string type_str;
        switch (token.type) {
            case TOKEN_DIGIT: type_str = "数字"; break;
            case TOKEN_ALPHA: type_str = "字母"; break;
            case TOKEN_PUNCT: type_str = "标点"; break;
            case TOKEN_EOF: type_str = "结束"; break;
        }
        cout << type_str << ": " << token.value << endl;
    }
    return 0;
}

3.2 应用 2：实现简单的正则表达式匹配（匹配 ab*c）

匹配规则：以 a 开头，后跟任意个 b，最后以 c 结尾（如 ac、abc、abbbc 均匹配）：

bool matchAbc(const string& s) {
    enum State { S0, S1, S2, S3 };
    State current = S0;
    for (char c : s) {
        switch (current) {
            case S0: // 初始态：等待 a
                if (c == 'a') current = S1;
                else return false;
                break;
            case S1: // 已匹配 a，等待 b 或 c
                if (c == 'b') current = S1; // 继续匹配 b
                else if (c == 'c') current = S2; // 匹配到 c，进入终止态
                else return false;
                break;
            case S2: // 终止态：后续字符无效
                return false;
            case S3: // 错误态
                return false;
        }
    }
    // 最终必须处于 S2（已匹配 c）
    return current == S2;
}

// 测试
int main() {
    cout << boolalpha;
    cout << matchAbc("ac") << endl;      // true
    cout << matchAbc("abc") << endl;     // true
    cout << matchAbc("abbbc") << endl;   // true
    cout << matchAbc("abx") << endl;     // false
    cout << matchAbc("a") << endl;       // false
    return 0;
}

3.3 应用 3：协议解析（模拟 TCP 握手状态机）

模拟 TCP 三次握手的状态转移：CLOSED → SYN_SENT → SYN_RECV → ESTABLISHED：

enum TCPState {
    CLOSED,
    SYN_SENT,
    SYN_RECV,
    ESTABLISHED
};

enum TCPEvent {
    EV_SYN,
    EV_SYN_ACK,
    EV_ACK
};

// 转移函数
TCPState tcpTransition(TCPState current, TCPEvent event) {
    switch (current) {
        case CLOSED:
            return (event == EV_SYN) ? SYN_SENT : CLOSED;
        case SYN_SENT:
            return (event == EV_SYN_ACK) ? SYN_RECV : SYN_SENT;
        case SYN_RECV:
            return (event == EV_ACK) ? ESTABLISHED : SYN_RECV;
        case ESTABLISHED:
            return ESTABLISHED;
        default:
            return CLOSED;
    }
}

// 测试三次握手
int main() {
    TCPState state = CLOSED;
    // 事件序列：SYN → SYN_ACK → ACK
    vector<TCPEvent> events = {EV_SYN, EV_SYN_ACK, EV_ACK};
    for (auto event : events) {
        state = tcpTransition(state, event);
        cout << "当前状态：";
        switch (state) {
            case CLOSED: cout << "CLOSED"; break;
            case SYN_SENT: cout << "SYN_SENT"; break;
            case SYN_RECV: cout << "SYN_RECV"; break;
            case ESTABLISHED: cout << "ESTABLISHED"; break;
        }
        cout << endl;
    }
    // 最终状态应为 ESTABLISHED
    cout << "握手是否成功：" << (state == ESTABLISHED) << endl;
    return 0;
}

四、有限状态自动机的优化与注意事项

4.1 优化技巧

1. 状态合并：将逻辑等价的状态合并，减少状态数量（如所有错误态可合并为一个）；
2. 输入分类：将相似输入合并为同一类型（如所有数字归为 INPUT_DIGIT），简化转移表；
3. 预编译转移表：对于固定规则的 DFA，可在编译期生成转移表（如用 constexpr），提升运行效率；
4. 惰性处理：对于长输入，可边读取边处理，无需一次性加载所有输入。

4.2 常见错误

1. 遗漏终止状态判断：仅处理完输入但未检查是否处于终止态（如手机号验证到 10 位就返回，未到 11 位）；
2. 状态转移不全：未覆盖所有'状态 + 输入'组合，导致空指针/未定义行为；
3. 错误态未处理：进入错误态后仍继续处理输入，导致逻辑错误；
4. 初始状态错误：未正确设置初始状态，导致整个自动机逻辑错误。

4.3 DFA vs NFA

• DFA：实现简单、效率高（每个输入仅一次状态转移），适合大部分实战场景；
• NFA：表达能力更强（支持正则表达式的 |、*、+ 等），但实现复杂，通常先转为 DFA 再使用。

五、总结

有限状态自动机是处理'基于上下文的输入处理'的核心工具，核心要点可总结为：

1. 核心思想：将复杂逻辑拆解为「状态」和「状态转移」，通过输入触发状态变化，最终到达终止态；
2. 实现模式：
   • 表驱动型：简洁易维护，适合简单规则（如验证、简单解析）；
   • 状态对象型：面向对象，易扩展，适合复杂规则（如协议解析、分词）；
   • 函数指针型：高性能，适合简单、高频调用的场景；
3. 核心优势：结构化、可扩展、可验证，避免冗长的 if-else/switch；
4. 应用场景：文本验证、协议解析、分词、正则匹配、游戏 AI、编译器前端等。

掌握有限状态自动机的关键：

• 先通过画图明确状态、输入、转移规则（可视化是理解的关键）；
• 优先选择表驱动型实现（简单场景），复杂场景再用状态对象型；
• 务必覆盖所有'状态 + 输入'组合，避免逻辑漏洞。

有限状态自动机是 AC 自动机、KMP 等字符串算法的底层思想，理解它能帮助你更深入地掌握这些高级算法，也是 C++ 开发者处理复杂逻辑的必备工具。