题目

标题和出处

标题：逆波兰表达式求值

出处：150. 逆波兰表达式求值

难度

4 级

题目描述

要求

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

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

注意整数除法向零取整。

给定的逆波兰表达式总是有效的。表达式总会得出有效数值且不存在除数为 的情况。

示例

示例 1：

输入：
输出：
解释：%20*%203)%20%3D%209%7D#card=math&code=%5Ctexttt%7B%28%282%20%2B%201%29%20%2A%203%29%20%3D%209%7D&id=XBLEO)

示例 2：

输入：
输出：
解释：)%20%3D%206%7D#card=math&code=%5Ctexttt%7B%284%20%2B%20%2813%20%2F%205%29%29%20%3D%206%7D&id=qBido)

示例 3：

输入：
输出：
解释：

%20%20-11)))%20%2B%2017)%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20((10%20%20(6%20%2F%20(12%20%20-11)))%20%2B%2017)%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20((10%20%20(6%20%2F%20-132))%20%2B%2017)%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20((10%20*%200)%20%2B%2017)%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20(0%20%2B%2017)%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%2017%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%2022%7D%0A%5Cend%7Baligned%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%26%20%5Cquad%20%5Ctexttt%7B%28%2810%20%2A%20%286%20%2F%20%28%289%20%2B%203%29%20%2A%20-11%29%29%29%20%2B%2017%29%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20%28%2810%20%2A%20%286%20%2F%20%2812%20%2A%20-11%29%29%29%20%2B%2017%29%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20%28%2810%20%2A%20%286%20%2F%20-132%29%29%20%2B%2017%29%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20%28%2810%20%2A%200%29%20%2B%2017%29%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%20%280%20%2B%2017%29%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%2017%20%2B%205%7D%20%5C%5C%0A%26%20%5Ctexttt%7B%3D%2022%7D%0A%5Cend%7Baligned%7D%0A&id=LwTdf)

数据范围

• 
• 或者是一个算符（、、 或 ），或者是一个在范围 内的整数

解法一

思路和算法

逆波兰表达式又称后缀表达式，由波兰的逻辑学家 J・卢卡西维兹于 1929 年提出。逆波兰表达式的特点是：没有括号，运算符总是放在和它相关的操作数之后，严格遵循从左到右的运算。

计算逆波兰表达式的值时需要使用栈存储操作数，从左到右遍历并计算。具体操作如下：

• 如果遇到操作数，则将操作数入栈；
• 如果遇到运算符，则将两个操作数出栈，其中先出栈的是第二个操作数，后出栈的是第一个操作数，使用运算符对两个操作数运算，得到新操作数，将新操作数入栈。

遍历结束之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

下图为示例 1 的计算逆波兰表达式的过程。

代码

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int length = tokens.length;
        for (int i = 0; i < length; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                case "+":
                    stack.push(num1 + num2);
                    break;
                case "-":
                    stack.push(num1 - num2);
                    break;
                case "*":
                    stack.push(num1 * num2);
                    break;
                case "/":
                    stack.push(num1 / num2);
                    break;
                default:
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String token) {
        return Character.isDigit(token.charAt(token.length() - 1));
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=STr2a)，其中 是数组 的长度。需要遍历数组 一次，计算逆波兰表达式的值。
• 空间复杂度：#card=math&code=O%28n%29&id=rgmo5)，其中 是数组 的长度。空间复杂度主要取决于栈空间，栈内元素个数不会超过逆波兰表达式的长度。

解法二

思路和算法

解法一使用栈存储操作数。也可以使用数组模拟栈操作。

对于长度为 的逆波兰表达式，其中有 个操作数和 个运算符。当遇到操作数时，将操作数入栈，栈内元素个数加 ；当遇到运算符时，将 个操作数出栈，使用运算符运算后得到 个新的操作数并入栈，因此栈内元素个数减 。根据上述分析可知，栈内元素个数不会超过原始逆波兰表达式中的操作数个数，即任何时候栈内元素个数不会超过 。因此，使用数组模拟栈操作时，将数组的长度定义为 即可。

数组的左端即下标 的位置为栈底。使用 表示栈顶元素所在下标，初始时 ，表示栈为空。

当元素入栈时，首先将 的值加 ，然后将入栈元素赋值到下标 处。

当元素出栈时，首先获得下标 处的元素，然后将 的值减 。

遍历结束之后，栈内只有一个元素，此时 ，位于下标 处的元素即为逆波兰表达式的值。

代码

class Solution {
    public int evalRPN(String[] tokens) {
        int length = tokens.length;
        int[] stack = new int[(length + 1) / 2];
        int top = -1;
        for (int i = 0; i < length; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack[++top] = Integer.parseInt(token);
            } else {
                int num2 = stack[top--];
                int num1 = stack[top--];
                switch (token) {
                case "+":
                    stack[++top] = num1 + num2;
                    break;
                case "-":
                    stack[++top] = num1 - num2;
                    break;
                case "*":
                    stack[++top] = num1 * num2;
                    break;
                case "/":
                    stack[++top] = num1 / num2;
                    break;
                default:
                }
            }
        }
        return stack[top];
    }
    public boolean isNumber(String token) {
        return Character.isDigit(token.charAt(token.length() - 1));
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=bszA7)，其中 是数组 的长度。需要遍历数组 一次，计算逆波兰表达式的值。
• 空间复杂度：#card=math&code=O%28n%29&id=ywl6S)，其中 是数组 的长度。空间复杂度主要取决于模拟栈操作的数组，其长度为 。