LeetCode 150. 逆波兰表达式求值

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/