題目

  • 題目連結
  • 目標函式 : evalRPN(tokens)
    • Input : tokens: List[str]
    • Output : int

解題概念

  • 題意 : 給定一字串陣列 tokens，代表一運算式的 Reverse Polish Notation (即 Prefix 格式)，需要去計算運算式，並回傳結果
  • 其中規則需要注意 :
    • Operators 包含 +、-、* 與 /
    • 兩個整數之間的除法總是截尾取零

我的寫法

  • 想法 : 這題是 Stack 題型中很經典的一題，而簡單來說每回合判斷邏輯如下
    • 若 tokens[i] 為數字，則直接將數字 push 到 Stack 中
    • 若 tokens[i] 為 Operator :
      1. 對 Stack 執行兩次 pop，取出兩個數字
      2. 對該兩個數字進行依照 Operator 進行運算
      3. 將計算結果 push 回 Stack 中
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def calculate(a, b, op):
            if op == "+":
                return a + b
            elif op == "-":
                return a - b
            elif op == "*":
                return a * b
            else: # 除法這裡要另外處理
                if a / b < 0 and a % b != 0:
                    return a // b + 1
                return a // b

        stack = []
        i = 0
        operators = ["+", "-", "*", "/"]
        
        while i < len(tokens):
            if tokens[i] not in operators: # tokens[i] 為數字
                stack.append(int(tokens[i]))
            else: # tokens[i] 為 Operators
                b = stack.pop(-1)
                a = stack.pop(-1)
                stack.append(calculate(a, b, tokens[i]))
            i += 1

        return stack[0] # 回傳最終結果
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 42 ms (faster than 74.63%)
    • Memory Usage: 15.3 MB (more than 71.45%)

解答 or 其他優秀寫法

  • 想法 :
    1. while 迴圈可以直接用 for 迴圈取代
    2. 把原本的 calculate() function 改成用 dict + lambda 去簡化，就不用另外去寫判斷的 if else 條件，是個很漂亮的寫法!
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def evalRPN(self, tokens):

        stack = []
        operators = {
            "+" : lambda a, b: a + b,
            "-" : lambda a, b: a - b,
            "*" : lambda a, b: a * b,
            "/" : lambda a, b: int(float(a) / b) 
        }
        for token in tokens:
            if token not in operators: # Digit
                stack.append(int(token))
            else: # Operators
                b = stack.pop(-1)
                a = stack.pop(-1)
                stack.append(operators[token](a, b))

        return stack[0]
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 40 ms (faster than 93.87%)
    • Memory Usage: 15.2 MB (more than 37.18%)