[26] 用 python 刷 Leetcode: 150 evaluate reverse polish notatio

原始题目

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((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

题目分析

这题是使用：逆波兰表示法，两个值之间的运算符号是表示在两个值後面
和一般日常使用写在中间的表示方式不太一样，遇到运算符才把前面「两个」数字做运算

解题过程

遍历传入的 Input，如果值不是运算符代表他是要运算的数字。转换成 int 存进堆叠里
遇到运算符号的时候，把堆叠最上面的两个值取出进行运算( python 3.8 没有 switch case 可以用)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for value in tokens:
            # 不是运算符就把值转成 int 存进 stack 里
            if value not in "+-*/":
                stack.append(int(value))
            # 防止第二的值就是运算符的防呆
            elif len(stack) > 1:
                # 遇到运算符的时候，取得堆叠最上面两个值进行运算
                num2 = stack.pop()
                num1 = stack.pop()

                if value == '+':
                    stack.append(num1 + num2)
                elif value == '-':
                    stack.append(num1 - num2)
                elif value == '*':
                    stack.append(num1 * num2)
                elif value == '/':
                    # 题目要求除法取整数就好
                    stack.append(int(num1 / num2))

        return stack[-1]