[Leetcode][python]Evaluate Reverse Polish Notation/逆波兰表达式求值
[Leetcode][python]Evaluate Reverse Polish Notation/逆波兰表达式求值
蛮三刀酱
发布于 2019-03-26 15:36:42
发布于 2019-03-26 15:36:42
题目大意
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 输入: [“2”, “1”, “+”, “3”, “*”] 输出: 9 解释: ((2 + 1) * 3) = 9
解题思路
参考：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()总结
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年06月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录