C++ 第42题：基于 std::stack 实现逆波兰表达式（RPN 后缀表达式求值）

题目

编写程序，利用 std::stack<long long> 对给定的逆波兰表达式（Reverse Polish Notation 后缀表达式，如 ["2", "1", "+", "3", "*"] 等价于 (2 + 1) * 3）进行解析与求值。支持 +, -, *, / 运算，且严格遵循减法与除法的操作数弹出先后顺序（先弹出者为右操作数，后弹出者为左操作数），并防御除零异常。

输入格式：无需外部输入（内置后缀表达式测试串）。

输出格式：输出逆波兰表达式计算出的数值结果。

数据范围与约定：运算过程符合 64 位整型范围，除数不为 0。

思路与算法

1. 逆波兰表达式的免括号特性
后缀表达式将运算符置于操作数之后，无需任何括号即可唯一确定运算先后级，是编译原理语法树计算的标准中间表示。

2. 操作数弹出顺序陷阱
对于非对称运算（减法与除法），从栈中弹出的第一个数是右操作数 b = st.top()，第二个数是左操作数 a = st.top()，计算公式必须为 a - b 与 a / b，切勿写反！

3. 流提取与数字判定
负数可能以 - 开头，因此判定是运算符还是负数时，需检测 token.size() > 1 || std::isdigit(token[0])。

完整程序

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <sstream>
#include <stdexcept>

long long evalRPN(const std::vector<std::string>& tokens) {
    std::stack<long long> st;

    for (const std::string& token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // 弹出两个操作数
            long long right = st.top(); st.pop();
            long long left = st.top(); st.pop();

            if (token == "+") st.push(left + right);
            else if (token == "-") st.push(left - right);
            else if (token == "*") st.push(left * right);
            else if (token == "/") {
                if (right == 0) throw std::runtime_error("除数为 0 错误");
                st.push(left / right);
            }
        } else {
            // 操作数直接压栈
            st.push(std::stoll(token));
        }
    }

    return st.top();
}

int main() {
    std::string line = "10 6 9 3 + -11 * / * 17 + 5 +";
    std::stringstream ss(line);
    std::vector<std::string> tokens;
    std::string token;
    while (ss >> token) {
        tokens.push_back(token);
    }

    std::cout << "后缀表达式: " << line << "\n";
    long long result = evalRPN(tokens);
    std::cout << "求值结果: " << result << "\n";

    return 0;
}

运行示例

输出：

后缀表达式: 10 6 9 3 + -11 * / * 17 + 5 +
求值结果: 22