C++ 实现字符串的逆波兰表达算法及其语法树构建核心解析【详解】

逆波兰表达式安全求值需严格分词、运算符优先判别、栈大小检查及除零防护；调试时可用vector替代stack；扩展支持一元负号需上下文识别，浮点数需variant与from_chars解析。

处理逆波兰表达式（RPN）时，最常见的坑就是：输入是一个以空格分隔的字符串，代码看起来逻辑没问题，结果一运行就崩溃，要么算出来的答案莫名其妙。别急，问题大概率出在 token 切分、弹栈顺序或者栈深度检查上。下面我们一步步把这件事理清。

一、基于 std::stack 的逆波兰表达式安全求值实现

如果你遇到了求值崩溃或结果异常，首先检查你是不是把 token 的类型判错了，或者弹栈的顺序搞反了。安全求值的核心逻辑其实就这几步：

1、用 std::istringstream 或者手动跳过空白字符的方式将输入字符串切成 tokens 向量，这一步要保证像 "-123"、"42" 这样的完整数字不被拆散。

2、遍历每个 token 时，先严格比对它是不是 "+"、"-"、"*"、"/" 这四个运算符字符串之一；只有不匹配的时候，才进入数字解析的分支。

3、对于非运算符 token，直接用 std::stoi(token) 转换，这个函数原生支持带符号整数（比如 "-5"、"+42"），不需要额外处理负号逻辑。

4、遇到运算符时，先检查 stack.size() >= 2，否则直接丢出一个 runtime_error。满足条件后按顺序弹出：int b = st.top(); st.pop(); int a = st.top(); st.pop();。

5、做除法之前，立刻判断 if (b == 0)，并抛出 "division by zero" 异常。减法和除法运算时一定要注意保持 a op b 的语义，左右操作数不能颠倒。

二、手写 vector 模拟栈以支持调试与中间状态观察

当你想验证每一步的计算过程、定位某次压栈或弹栈的异常、或者排查一个非法 token 导致的静默失败时，std::stack 就有点捉襟见肘了——它不提供遍历接口。这时候改用 std::vector 会顺手很多：你可以显式控制栈顶索引，还能把整栈内容打印出来瞧瞧。

1、声明 std::vector stack 替代 std::stack，所有 push 操作改为 stack.push_back(value)。

2、弹出右操作数时：int b = stack.back(); stack.pop_back();，再弹左操作数：int a = stack.back(); stack.pop_back();。

3、每次关键操作之后可以插入 for (auto x : stack) std::cout << x << " "; 输出当前栈状态，方便调试。

4、在运算符处理入口处加一句 if (stack.size() < 2) throw ...，防止非法表达式。

5、对非法 token（比如 "abc" 或空字符串），在调用 stoi 之前先做长度和首字符校验：if (token.empty() || (token.size() == 1 && !std::isdigit(token[0]))) throw std::invalid_argument("invalid token: " + token);。

三、构建抽象语法树（AST）节点结构与递归构造逻辑

如果你需要从逆波兰表达式反向生成语法树——比如用于可视化、类型检查或代码生成——就不能直接复用求值栈的逻辑了。你需要维护一个节点指针栈，遇到运算符时合并子树根节点。

1、定义 AST 节点结构：struct Node { std::string val; Node* left = nullptr; Node* right = nullptr; explicit Node(const std::string& v) : val(v) {} };

2、初始化 std::stack node_stack，然后遍历 tokens：如果 token 是数字，new Node(token) 并压栈；如果是运算符，弹出两个节点作为 right 和 left 子树。

3、构造新节点时注意顺序：Node* op_node = new Node(token); op_node->right = right; op_node->left = left;，因为 right 先弹出，所以它应该作为右子树。

4、把 op_node 压入 node_stack；循环结束后，栈中唯一的那个节点就是 AST 的根节点。

5、为了防止内存泄漏，要么在析构函数或 RAII 容器中递归 delete 所有节点，要么改用 std::unique_ptr 来管理所有权。

四、使用 std::from_chars 替代 std::stoi 实现无异常数字解析

在高可靠性场景中，std::stoi 抛出异常可能会打断控制流，而且无法区分是数值溢出还是格式错误。C++17 引入的 std::from_chars 是零开销解析接口，它返回错误码而非异常，更适合嵌入式或服务端批量处理。

1、为每个 token 声明 std::from_chars_result res; 和目标变量 long long temp_val = 0;。

2、调用 res = std::from_chars(token.data(), token.data() + token.size(), temp_val);。

3、检查 if (res.ec == std::errc::invalid_argument || res.ec == std::errc::result_out_of_range)，然后触发自定义错误处理路径。

4、确认解析完整性：if (res.ptr != token.data() + token.size()) 表示存在尾随非法字符（例如 "123abc"），应视为非法 token。

5、将 temp_val 转为 int 之前，增加 if (temp_val < INT_MIN || temp_val > INT_MAX) 判断溢出，避免截断导致的静默错误。

五、支持一元负号与浮点数的扩展 token 分类机制

标准逆波兰表达式规范通常不包含一元运算符，但实际输入中很可能出现 "-5"（此时它是一个操作数）和 "5 -"（二元减）共存的情况。需要通过上下文识别一元负号，避免把它误判成减法运算符。

1、预扫描 tokens 序列，记录每个 token 的前驱 token 类型：如果前驱为空、是 "(" 或者是运算符，那么当前这个 "-" 就视为一元负号。

2、对于识别为一元负号的 token，跳过运算符分支，直接按数字解析（比如 stoi("-5")），在 AST 构造中生成 UnaryMinus 节点而不是 BinaryOp。

3、如果需要支持浮点数，把 token 判定逻辑扩展成：先尝试 std::from_chars 解析 double，失败再试整数，最后才判运算符。

4、在 vector 模拟栈中，统一使用 std::variant 存储值类型，配合 std::holds_alternative 和 std::get 提取。

5、对于浮点除法，禁用向零截断，直接使用 / 运算符，并在 AST 中标记 type = FLOAT，确保后续类型推导的一致性。