150 逆波兰表达式

题目 150 逆波兰表达式

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

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

注意 两个整数之间的除法只保留整数部分。

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

思路

• 什么是逆波兰表达式：
  逆波兰式（或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。
  如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+

• 用处：波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

• 思路：用栈的结构解决：循环字符串，如果碰到数字就入栈，乳沟碰到运算符就出栈两个元素进行运算（注意两个数字的前后顺序），结果再入栈。

代码

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens:
            if i == "+" or i == "-" or i == "*" or i == "/":
                num1 = stack.pop()
                num2 = stack.pop()
                if i == "+":
                    stack.append(int(num2)+int(num1))
                if i == "-":
                    stack.append(int(num2)-int(num1))
                if i == "*":
                    stack.append(int(num2)*int(num1))
                if i == "/":
                    # 特别注意，这里就是用地板除法，结果再int一下，不然会有6//-132=-1的情况，但是题目实际是要求等于0的。
                    stack.append(int(int(num2)/int(num1)))
            else:
                stack.append(int(i))
        return stack[0]

留有疑问，希望看到的博友能解答一下

为什么 6/-132=-1？可能时间长了，最基础的知识都忘掉了。。。哎