【C++经典例题】逆波兰表达式求值：栈的经典应用与实现详解

@[toc]

题目描述

给定一个逆波兰表达式（后缀表达式），计算其对应的算术值。表达式中的操作数和运算符通过字符串数组 tokens 给出，要求返回最终计算结果。

示例：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：(2 + 1) * 3 = 9

逆波兰表达式基础

1. 什么是逆波兰表达式？

逆波兰表达式（Reverse Polish Notation, RPN）是一种数学表示法，其特点是将运算符置于操作数的后面。例如：

• 中缀表达式 (2 + 1) * 3 → 后缀表达式 ["2","1","+","3","*"]
• 中缀表达式 4 / (13 + 5) → 后缀表达式 ["4","13","5","+","/"]

逆波兰表达式的优势是无需括号即可明确运算顺序，且适合计算机通过栈结构高效处理。

2. 核心计算规则

1. 从左到右遍历表达式。
2. 遇到操作数则压入栈中。
3. 遇到运算符则弹出栈顶两个元素，按运算符计算后，将结果压回栈中。
4. 最终栈中唯一的元素即为结果。

解题思路与代码实现

1. 为什么用栈？

• 后进先出特性：逆波兰表达式的计算顺序天然符合栈的操作逻辑。运算符作用于最近的两个操作数，栈能快速提供这两个数。
• 时间复杂度：所有元素仅遍历一次，时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况下栈中存储所有操作数）。

2. 代码实现解析

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (const string& s : tokens) { // 遍历每个token
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                // 弹出右操作数（先弹出的是右）
                int right = st.top(); st.pop();
                int left = st.top(); st.pop();
                // 根据运算符计算并压栈
                switch (s[0]) {
                    case '+': st.push(left + right); break;
                    case '-': st.push(left - right); break;
                    case '*': st.push(left * right); break;
                    case '/': st.push(left / right); break;
                }
            } else {
                // 操作数直接压栈
                st.push(stoi(s));
            }
        }
        return st.top();
    }
};

3. 关键细节剖析

1. 操作数顺序问题：

   • 在弹栈时，先弹出的是右操作数，后弹出的是左操作数。
   • 例如表达式 ["4","13","5","+","/"]，当处理到 / 时，栈顶为 [4, 18]，弹出顺序为 right=18 和 left=4，因此实际计算的是 4 / 18 = 0（向零取整）。

2. 除法截断规则：

   • C++中整数除法默认向零取整（如 6 / -4 = -1），与题目要求一致，因此无需额外处理。

3. 字符串转整数：

   • 使用 stoi(s) 将字符串转换为整数，题目保证输入的合法性，无需处理异常。

边界条件与测试用例

1. 边界情况

• 单操作数：输入 ["42"] → 输出 42。
• 负数与除法：输入 ["6","-4","/"] → 输出 -1。
• 连续运算符：输入 ["3","4","+","2","*"] → 输出 (3+4)*2=14。

2. 测试用例验证

输入：["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
步骤分解：
  1. 9+3=12 → 压入12
  2. -11*12=-132 → 压入-132
  3. 6/-132=0 → 压入0
  4. 10*0=0 → 压入0
  5. 0+17=17 → 压入17
  6. 17+5=22 → 结果为22

总结

逆波兰表达式求值问题通过栈结构高效解决了运算顺序问题，代码简洁且符合直觉。核心要点包括：

1. 栈的灵活应用：操作数压栈、运算符弹栈计算。
2. 操作数顺序：先右后左，确保减法和除法正确性。
3. 语言特性利用：C++的整数除法规则与题目要求一致。

该问题涉及到的细节问题较多，掌握此问题有助于深入理解栈在表达式计算中的经典应用，同时为后续学习编译原理中的语法解析打下基础。