题目描述

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

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

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

样例

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

算法1

(暴力枚举) $O(n)$ 每个元素仅遍历一次

遍历所有元素：
1.如果当前元素是整数，则压入栈；
2.如果是运算符，则将栈顶两个元素弹出做相应运算，再将结果入栈。
–> 最终表达式扫描完后，栈里的数就是结果。

时间复杂度

参考文献

python 代码

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk=[]
        for x in tokens:
            if x=="+" or x=="-" or x=="*" or x=="/":
                a=stk.pop()
                b=stk.pop()
                if x=="+":stk.append(a+b)
                elif x=="-":stk.append(b-a)
                elif x=="*":stk.append(a*b)
                #难点1.除法取整
                else:stk.append(int(b/a))
            else:
                #难点2.x要从字符串变成整数（即去除引号“”）
                stk.append(int(x))
        return stk[0]