🥈medium - 🥈 150. 逆波兰表达式求值 - 《算法与LeetCode题解》

题解

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

说明：

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

给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 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 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
题解
这道题还挺简单的，比之前的简单计算器容易多了，不用考虑太多！
🥇 224. 基本计算器
 🥈 227. 基本计算器 II
就是把数字放到栈里面，遇到符号就弹出两个运算数，再将计算结果放到栈里面。最后栈里面只有一个最后的答案，输出即可！

不过Python的负数整除真的是好坑！！🧘🏻‍♂️
下面写的就有问题，在除法上被坑了！而且写的不太简洁

Python

Python除法

python 的整数除法是向下取整，而不是向零取整。

python2 的除法 “/“ 是整数除法， “-3 / 2 = -2” ；
python3 的地板除 “//“ 是整数除法， “-3 // 2 = -2” ；
python3 的除法 “/“ 是浮点除法， “-3 / 2 = -1.5” ；

而 C++/Java 中的整数除法是向零取整。

C++/Java 中 “-3 / 2 = -1” .

本题的题意（一般情况）都是要求向零取整的。

解决方法 1

对 Python 的整数除法问题，可以用 int(num1 / float(num2)) 来做，即先用浮点数除法，然后取整。

无论如何，浮点数除法都会得到一个浮点数，比如 “-3 / 2.0 = 1.5“ ；
此时再取整，就会得到整数部分，即float(-1.5) = -1 。
解决方法 2
使用库函数 operator.truediv(num1, num2) ，调用该函数等价于 num1 / float(num2)。

❌ 错误代码

下面是错误的代码：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack=[]
        calcute = ['+','-','*','/']
        for i in tokens:
            ans=0
            if i not in calcute:
                stack.append(int(i))
                print(i,stack)
            else:
                a = stack.pop()
                b = stack.pop()
                print(a,b)
                if i == '+':
                    ans = a+b
                elif i == '-':
                    ans = b-a
                elif i == '*':
                    ans = a*b
                else:
                    ans = abs(b) // abs(a) * (-1 if a*b<0 else 1)
                stack.append(ans)
        return stack[0]

✔️ 正确代码

下面是两种正确的代码，参考一下：

class Solution(object):
    def evalRPN(self, tokens):
        stack = []
        for token in tokens:
            try:
                stack.append(int(token))
            except:
                num2 = stack.pop()
                num1 = stack.pop()
                stack.append(self.evaluate(num1, num2, token))
        return stack[0]

    def evaluate(self, num1, num2, op):
        if op == "+":
            return num1 + num2
        elif op == "-":
            return num1 - num2
        elif op == "*":
            return num1 * num2
        elif op == "/":
            return int(num1 / float(num2))

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op_to_binary_fn = {
            "+": add,
            "-": sub,
            "*": mul,
            "/": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致
        }

        stack = list()
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                num2 = stack.pop()
                num1 = stack.pop()
                num = op_to_binary_fn[token](num1, num2)
            finally:
                stack.append(num)

        return stack[0]

JavaScript

var evalRPN = function(tokens) {
    const stack = [];
    const n = tokens.length;
    for (let i = 0; i < n; i++) {
        const token = tokens[i];
        if (isNumber(token)) {
            stack.push(parseInt(token));
        } else {
            const num2 = stack.pop();
            const num1 = stack.pop();
            if (token === '+') {
                stack.push(num1 + num2);
            } else if (token === '-') {
                stack.push(num1 - num2);
            } else if (token === '*') {
                stack.push(num1 * num2);
            } else if (token === '/') {
                stack.push(num1 / num2 > 0 ? Math.floor(num1 / num2) : Math.ceil(num1 / num2));
            }
        }
    }
    return stack.pop();
};

const isNumber = (token) => {
    return !('+' === token || '-' === token || '*' === token || '/' === token );
}

复杂度分析

时间复杂度：，其中 n 是数组 tokens 的长度。需要遍历数组 tokens 一次，计算逆波兰表达式的值。
空间复杂度：，其中 n 是数组 tokens 的长度。使用栈存储计算过程中的数，栈内元素个数不会超过逆波兰表达式的长度。

🥈 150. 逆波兰表达式求值

题解