📃 题目描述

题目链接：

• 剑指 Offer II 036. 后缀表达式 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。

给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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

🔔 解题思路

这个题目比较简单的点就在于没有括号，哪个符号在前哪个符号就先算

所以思路就很简单了：

• 遍历字符依次入栈，遇到符号就将栈顶的两个元素出栈进行计算，然后将计算结果再入栈

class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();

        for (String s : tokens) {
            // 遍历字符依次入栈，遇到符号就将栈顶的两个元素出栈进行计算，然后将计算结果再入栈
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int op1 = stack.pop();
                int op2 = stack.pop();
                int res = 0;
                switch (s) {
                    case "+":
                        res = op2 + op1;
                        break;
                    case "-":
                        res = op2 - op1;
                        break;
                    case "*":
                        res = op2 * op1;
                        break;
                    case "/":
                        res = op2 / op1;
                        break;
                }
                stack.push(res);
            } 
            // 如果栈为空 or s 是数字的话，直接入栈
            else {
                stack.push(new Integer(s));
            }
        }

        // 栈中的最后一个元素就是最终结果
        return stack.pop();
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)