150. 逆波蘭表達式求值

題目

根據(jù)逆波蘭表示法，求表達式的值。有效的算符包括 +、-、*、/ 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。注意兩個整數(shù)之間的除法只保留整數(shù)部分?？梢员ＷC給定的逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

例：
輸入：tokens = ["2","1","+","3",""]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9*

方法

• 若該字符是數(shù)字，則壓入棧
• 若該字符是運算符號，則移除并返回棧頂元素和次棧頂元素，并進行計算
• 需要注意的是：首先字符的類型為字符串，為了之后的計算應將數(shù)字轉化為整數(shù)型。其次，由于 python 的除法為向下取整，例如：int(6/-132) = -1 ≠ 0。為了實現(xiàn)向零取整，可以使用將除數(shù)轉化為浮點型，然后將計算結果取整。

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 的形式為字符串，而非整數(shù)，需將其轉化為整型

參考

逆波蘭表達式：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/