[Leetcode][python]Evaluate Reverse Polish Notation/逆波兰表达式求值

素颜马尾好姑娘i 2022-05-22 10:12 163阅读 0赞

## 题目大意 ##

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

*  整数除法只保留整数部分。
 *  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
    
    输入: \[“2”, “1”, “+”, “3”, “\*”\]  
    输出: 9  
    解释: ((2 + 1) \* 3) = 9

## 解题思路 ##

参考：[https://www.cnblogs.com/zuoyuan/p/3760530.html][https_www.cnblogs.com_zuoyuan_p_3760530.html]  
解题思路：这道题是经典的逆波兰式求值。具体思路是：开辟一个空栈，遇到数字压栈，遇到运算符弹出栈中的两个数进行运算，并将运算结果压栈，最后栈中只剩下一个数时，就是所求结果。这里需要注意的一点是python中的’/’除法和c语言不太一样。在python中，(-1)/2=-1，而在c语言中，(-1)/2=0。也就是c语言中，除法是向零取整，即舍弃小数点后的数。而在python中，是向下取整的。而这道题的oj是默认的c语言中的语法，所以需要在遇到’/’的时候注意一下。

## 代码 ##

class Solution:
        # @param tokens, a list of string
        # @return an integer
        def evalRPN(self, tokens):
            stack = []
            for i in range(0,len(tokens)):
                if tokens[i] != '+' and tokens[i] != '-' and tokens[i] != '*' and tokens[i] != '/':
                    stack.append(int(tokens[i]))
                else:
                    a = stack.pop()
                    b = stack.pop()
                    if tokens[i] == '+':
                        stack.append(a+b)
                    if tokens[i] == '-':
                        stack.append(b-a)
                    if tokens[i] == '*':
                        stack.append(a*b)
                    if tokens[i] == '/':
                        if a*b < 0:
                            stack.append(-((-b)/a))
                        else:
                            stack.append(b/a)
            return stack.pop()

## 总结 ##

[https_www.cnblogs.com_zuoyuan_p_3760530.html]: https://www.cnblogs.com/zuoyuan/p/3760530.html