c++中如何实现后缀表达式求值_c++栈实现逆波兰表达式计算

用std::stack计算后缀表达式时，需逐token判断类型：运算符则弹出b、a并计算a op b；数字直接stoi（支持负数）；须检查空栈、除零及非法token。

用 std::stack 处理数字和运算符的分离

后缀表达式（逆波兰表达式）没有括号，运算符紧随其操作数之后，天然适合栈处理：遇到数字就压栈，遇到运算符就弹出两个操作数（注意顺序），计算后再压栈。关键在于准确识别 token 类型——不能简单按空格切分后直接 std::stoi，因为负数如 "-5" 会被误判为运算符 "-" 加数字 "5"。

实操建议：

• 逐字符扫描，或用 std::stringstream 按空格分割，但对每个 token 先检查是否为 "+"、"-"、"*"、"/" 四个运算符之一；只有不匹配时才当作数字解析
• 负数字符串（如 "-123"）会被 std::stoi 正确处理，无需特殊逻辑；但单个 "-" 必须排除在数字解析之外
• 除法需向零截断（C++ 中 int 除法默认如此），但要注意被除数为负、除数为正等情况下的行为一致性

运算符弹栈顺序不能反——第二个弹出的是左操作数

栈是后进先出，所以对表达式 "3 4 +"，先压 3，再压 4；遇到 "+" 时，先弹出 4（右操作数），再弹出 3（左操作数），然后算 3 + 4。如果顺序颠倒，减法和除法结果必然错误。

常见错误现象：

• "5 2 -" 算成 2 - 5 == -3（错），正确应为 5 - 2 == 3
• "7 2 /" 算成 2 / 7 == 0（错），正确应为 7 / 2 == 3

务必写成：

int b = stack.top(); stack.pop();
int a = stack.top(); stack.pop();
int res = a op b;

输入合法性检查不能省——空栈或除零要提前拦截

真实输入可能非法：运算符多于数字（如 "1 +"）、除零（"5 0 /"）、非数字非运算符（"1 @ 2 +"）。不检查会导致运行时崩溃或未定义行为。

使用场景中必须包含：

• 每次执行运算前，用 stack.size() 判断是否足够弹出两个操作数；不够则抛异常或返回错误码
• 遇到 "/" 或 "%" 时，检查第二个弹出的数（即除数）是否为 0
• token 解析失败（如 std::stoi 抛 std::invalid_argument）应统一捕获并处理

完整可跑的最小实现示例（支持负数、四则运算、基础错误处理）

以下代码聚焦核心逻辑，去掉了输入读取封装，直接以 std::vector<:string> 模拟 token 序列：

#include 
#include 
#include 
#include 
#include 
int evalRPN(const std::vector& tokens) {
std::stack stk;
for (const auto& t : tokens) {
if (t == "+" || t == "-" || t == "" || t == "/") {
if (stk.size() < 2) throw std::runtime_error("insufficient operands");
int b = stk.top(); stk.pop();
int a = stk.top(); stk.pop();
if (t == "+") stk.push(a + b);
else if (t == "-") stk.push(a - b);
else if (t == "") stk.push(a * b);
else if (t == "/") {
if (b == 0) throw std::runtime_error("division by zero");
stk.push(a / b); // C++ truncates toward zero
}
} else {
try {
stk.push(std::stoi(t));
} catch (const std::exception&) {
throw std::runtime_error("invalid token: " + t);
}
}
}
if (stk.size() != 1) throw std::runtime_error("too many operands");
return stk.top();
}

真正容易被忽略的是：最后必须验证栈只剩一个元素。多个独立数字（如 {"1", "2", "3"}）不会触发任何运算，但这是非法后缀表达式——没人会写，但程序得拦住。