LC150. 逆波兰表达式求值

题目描述

根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 注意 两个整数之间的除法只保留整数部分，向零截断。 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1： 输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 示例 2： 输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 示例 3： 输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 提示： 1 <= tokens.length <= 10^4 tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数 逆波兰表达式： 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 逆波兰表达式主要有以下两个优点： 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + *也可以依据次序计算出正确结果。 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

题目解析

题目在说什么

想象你是一个计算器，但你的输入方式很特别——不是我们平时写的“1+2”，而是把运算符放到后面，比如“1 2 +”。这就是逆波兰表达式，也叫后缀表达式。

题目给你一个字符串数组，里面要么是数字，要么是运算符（+、-、*、/）。你要按照这个顺序去计算，最后得到一个结果。注意除法要“向零截断”，就是直接舍去小数部分，比如 13/5=2（不是2.6），-13/5=-2（不是-2.6）。

思路是怎么来的

生活化比喻：想象你在玩一个“数字叠叠乐”的游戏。

你面前有一叠卡片，每张卡片上要么是数字，要么是运算符。你按顺序一张张看卡片：

• 如果看到数字卡片，你就把它放进一个“数字盒子”里（这个盒子一次只能拿最上面的那张）。
• 如果看到运算符卡片（比如“+”），你就从盒子里拿出最上面的两张数字卡片，用这个运算符算一下，然后把结果放回盒子里。

这样一直做下去，最后盒子里只剩一张卡片，那就是最终答案。

为什么这样能行？ 因为逆波兰表达式已经帮我们排好了顺序——数字先来，运算符后来。每次遇到运算符，它要用的两个数字正好就在盒子的最上面（因为刚放进去）。这个“盒子”其实就是栈（Stack），它就像一叠盘子，只能从最上面拿，也只能往最上面放。

关键点：

• 先拿出来的数字是“右操作数”，后拿出来的是“左操作数”。比如看到“-”，先拿出的是右边的数，再拿出左边的数，然后做“左 - 右”。
• 除法要“向零截断”，在Python里用int(左 / 右)来实现，因为//对负数会向下取整（比如-3//2=-2，但我们想要-1）。

代码逐步拆解

我们来看参考代码（Java版），但我会用最通俗的方式解释每一步在干嘛。

class Solution {
    public int evalRPN(String[] tokens) {
        // 1. 准备一个“数字盒子”（栈）
        Stack<Integer> result = new Stack<>();
        
        // 2. 准备三个临时变量
        int rightNum;  // 右操作数（先拿出来的）
        int leftNum;   // 左操作数（后拿出来的）
        int ans;       // 计算结果
        
        // 3. 一张一张看卡片
        for(String token : tokens){
            // 如果卡片是运算符
            if("+".equals(token)){
                rightNum = result.pop();  // 拿出最上面的数字（右操作数）
                leftNum = result.pop();   // 再拿出下一个数字（左操作数）
                ans = leftNum + rightNum; // 计算
            }else if("-".equals(token)){
                rightNum = result.pop();
                leftNum = result.pop();
                ans = leftNum - rightNum; // 注意顺序：左 - 右
            }else if("*".equals(token)){
                rightNum = result.pop();
                leftNum = result.pop();
                ans = leftNum * rightNum;
            }else if("/".equals(token)){
                rightNum = result.pop();
                leftNum = result.pop();
                ans = leftNum / rightNum; // 整数除法，自动向零截断
            }else{
                // 如果卡片是数字，直接转成整数
                ans = Integer.valueOf(token);
            }
            
            // 4. 把结果放回盒子
            result.push(ans);
        }
        
        // 5. 最后盒子里只剩一个数字，就是答案
        return result.pop();
    }
}

**逐步拆解（用示例["2","1","+","3","*"]演示）**：

1. 初始：盒子是空的 []。