模擬: 逆序波蘭表達式的計算 Evaluate Reverse Polish Notation_Leetcode 150

Chris Liverani on Unsplash

題目敘述

題目會給我們一個輸入陣列tokens，裡面以逆序波蘭表達式的方式儲存各個token，請問最後計算完的值是多少?

例如: ["6", "2", "/"]

代表 6 / 2 =3

題目的原文敘述

測試範例

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

約束條件

Constraints:

• 1 <= tokens.length <= 10^4

輸入陣列的長度1 ~ 一萬之間。

• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

每個token一定是四則運算符號，或者介於-200~200之間的整數。

演算法 用stack進行模擬

這題應該滿多讀者在以前的資料結構或者演算法上課的時候看過類似的題目，給一串波蘭表達式，對這個波蘭表達式計算求值。

這題也是，而且已經講明了是逆序表達式，也就是說，所有的計算順序可以抽象的表達成:

日常生活中的 a 運算子 b <=> 以 a, b, 運算子 的逆序波蘭表達式出現

其中，運算子可以是 加+, 減-, 乘*, 除/

題目還規定，做除法的時候一率Truncate to zero，捨去小數點部分。

模擬的時候，先建立一個空的stack，依序掃描每個token。

假如遇到數字，就把這個數字轉型為int，推入到stack的頂端儲存起來。

假如遇到四則運算子，就pop出來最頂端的兩個運算元，用對應的運算子去計算，再把計算完的值推入stack的頂端。

程式碼 用stack進行模擬

class Solution(object):
    def evalRPN(self, tokens):

        # Use stack to store operands        
        stack = []

        operator = set("+-*/")

        for token in tokens:

            if token not in operator:
                # Casting from string to integer
                stack.append( int(token) )
                continue

            # Get first operand and second operand
            second, first= stack.pop(), stack.pop()

            if token == "+":
                result = first + second
            elif token == "-":
                result = first - second
            elif token == "*":
                result = first * second
            else:
                # Truncates toward zero, defined in description
                result = int(first / second)

            stack.append(result)
        # ========================================
        return stack.pop()

複雜度分析 用stack進行模擬

時間複雜度:

從左到右檢查每個token，每個token最多push, pop各一次，所需時間為O(n)。

空間複雜度:

需要一個stack去儲存每個operand，所需空間最長為O(n)。

關鍵知識點

日常生活中的 a 運算子 b <=> 以 a, b, 運算子 的逆序波蘭表達式出現

其中，運算子可以是 加+, 減-, 乘*, 除/

題目還規定，做除法的時候一率Truncate to zero，捨去小數點部分。

模擬的時候，先建立一個空的stack，依序掃描每個token。

假如遇到數字，就把這個數字轉型為int，推入到stack的頂端儲存起來。

假如遇到四則運算子，就pop出來最頂端的兩個運算元，用對應的運算子去計算，再把計算完的值推入stack的頂端。