题目描述

根据逆波兰表示法（Reverse Polish Notation，RPN），求表达式的值。有效的算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。

解题思路

逆波兰表达式是一种后缀表达式，其特点是将运算符放在操作数之后。计算逆波兰表达式非常适合使用栈数据结构。

核心思路：遍历 tokens 数组中的每一个字符串：

  1. 如果当前字符串是数字（操作数），直接将其转换为整数并入栈。
  2. 如果当前字符串是运算符（+、-、*、/），则从栈中弹出两个操作数（注意弹出顺序：先弹出的是第二个操作数 num2，后弹出的是第一个操作数 num1），根据运算符执行相应的计算，并将计算结果压回栈中。

当遍历完所有 token 后，栈中剩下的唯一一个元素就是整个表达式的计算结果。

关键细节：

  • 由于减法和除法不满足交换律，操作数的顺序很重要。在逆波兰表达式中，遇到运算符时，栈顶元素是右操作数，次栈顶元素是左操作数。例如对于 ["4", "3", "-"]，先入栈 4，再入栈 3，遇到 - 时弹出 3 作为右操作数、4 作为左操作数，计算 4 - 3 = 1。
  • 除法按题目要求保留整数部分，Java 中的整数除法天然满足这个要求。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是 tokens 数组的长度。只需要遍历一次数组，每次入栈、出栈操作为 O(1)。
  • 空间复杂度：O(n)，栈中最多存储 n 个操作数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package code.J150;

import java.util.ArrayDeque;
import java.util.Deque;

public class J150 {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String s : tokens) {
            if ("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (s) {
                    case "+": stack.push(num1 + num2); break;
                    case "-": stack.push(num1 - num2); break;
                    case "*": stack.push(num1 * num2); break;
                    case "/": stack.push(num1 / num2); break;
                }
            } else {
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
}