150. 逆波兰表达式求值
题目
根据逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
例：
输入：tokens = ["2","1","+","3",""]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9*
方法
- 若该字符是数字，则压入栈
- 若该字符是运算符号，则移除并返回栈顶元素和次栈顶元素，并进行计算
- 需要注意的是：首先字符的类型为字符串，为了之后的计算应将数字转化为整数型。其次，由于 python 的除法为向下取整，例如：int(6/-132) = -1 ≠ 0。为了实现向零取整，可以使用将除数转化为浮点型，然后将计算结果取整。
class Solution(object):
def evalRPN(self, tokens):
record = []
for item in tokens:
if item not in {'+', '-', '*', '/'}:
record.append(int(item))
else:
num2, num1 = record.pop(), record.pop()
if item == '+':
temp = num1 + num2
elif item == '-':
temp = num1 - num2
elif item == '*':
temp = num1 * num2
else:
temp = int(num1 / float(num2))
record.append(temp)
return record[0]
相关知识
-
逆波兰表达式：
后缀表达式。我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
例：
(a+b)c-(a+b)/e
→((a+b)c)((a+b)/e)-
→((a+b)c)((a+b)e/)-
→(ab+c)(ab+e/)-
→ab+cab+e/-*
报错
此时，a 和 b 的形式为字符串，而非整数，需将其转化为整型
参考
逆波兰表达式：https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437?fr=aladdin
向零取整：https://leetcode.cn/problems/evaluate-reverse-polish-notation/solution/xiang-jie-ni-bo-lan-biao-da-shi-fu-ben-t-sfl6/
