C++算法
C++ 有限状态自动机（FSM）：原理、实现与应用全解析
本文详解 C++ 有限状态自动机（FSM）的原理与实现。涵盖核心概念定义（状态、输入、转移函数），三种主流实现模式（表驱动型、状态对象型、函数指针型）。通过手机号验证、键值对解析、文本分词、正则匹配及 TCP 协议模拟等实战案例，展示 FSM 在复杂逻辑结构化中的应用。同时提供优化技巧与常见错误分析，帮助开发者掌握基于状态转移的编程思想，提升代码可维护性与扩展性。
本文详解 C++ 有限状态自动机（FSM）的原理与实现。涵盖核心概念定义（状态、输入、转移函数），三种主流实现模式（表驱动型、状态对象型、函数指针型）。通过手机号验证、键值对解析、文本分词、正则匹配及 TCP 协议模拟等实战案例，展示 FSM 在复杂逻辑结构化中的应用。同时提供优化技巧与常见错误分析，帮助开发者掌握基于状态转移的编程思想，提升代码可维护性与扩展性。
有限状态自动机（Finite State Machine, FSM，也叫有限状态机）是一种抽象计算模型，核心思想是将复杂的逻辑拆解为「状态」和「状态转移」，通过输入触发状态变化，最终完成特定逻辑处理。它广泛应用于编译器、协议解析、文本处理、游戏 AI 等场景，也是实现 AC 自动机、KMP 等算法的底层思想。本文将从核心原理、分类、C++ 实现模式到实战案例，全面解析有限状态自动机的设计与落地技巧。
面对需要根据'上下文/历史输入'做决策的场景（如解析 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;
}
这种写法在规则复杂时（如支持带区号、分机号的手机号）会迅速失控。
有限状态自动机的核心价值：
一个有限状态自动机由 5 个核心元素组成（五元组）：
δ(current_state, input) → next_state，定义'当前状态 + 输入'对应的下一个状态。分类：
示例：验证'11 位手机号（以 1 开头，后 10 位为数字）'的 DFA：
有限状态自动机的实现有多种模式，从简单到复杂依次为：表驱动型、状态对象型、函数指针/回调型，其中表驱动型是实战中最常用的方式。
核心思想：用二维数组/哈希表存储转移规则，通过查表实现状态转移，代码结构清晰、易扩展。
#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 → 无效
核心思想：将每个状态封装为类/对象，状态转移由对象自身处理，符合开闭原则（新增状态无需修改原有代码）。
#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= → 解析失败
核心思想：用函数指针/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;
}
实现一个分词器，提取文本中的'数字''字母''标点'三类 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;
}
匹配规则：以 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;
}
模拟 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;
}
有限状态自动机是处理'基于上下文的输入处理'的核心工具，核心要点可总结为：
掌握有限状态自动机的关键：
有限状态自动机是 AC 自动机、KMP 等字符串算法的底层思想，理解它能帮助你更深入地掌握这些高级算法，也是 C++ 开发者处理复杂逻辑的必备工具。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online