[LeetCode] #150 Evaluate Reverse Polish Notation (Medium)
LeetCode 第 150 題 Evaluate Reverse Polish Notation，難度 Medium
用 Python3 解 LeetCode 系列，Evaluate Reverse Polish Notation，屬於 Medium
原始題目
Evaluate the value of an arithmetic expression in Reverse Polish Notation .
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
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
題目分析
這題是使用：逆波蘭表示法
，兩個值之間的運算符號是表示在兩個值後面
和一般日常使用寫在中間的表示方式不太一樣 ，遇到運算符才把前面「兩個」數字做運算
解題過程
- 遍歷傳入的 Input，如果值不是運算符代表他是要運算的數字。轉換成 int 存進堆疊裡
- 遇到運算符號的時候，把堆疊最上面的兩個值取出進行運算( python 3.8 沒有 switch case 可以用)
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for value in tokens:
# 不是運算符就把值轉成 int 存進 stack 裡
if value not in "+-*/":
stack.append(int(value))
# 防止第二的值就是運算符的防呆
elif len(stack) > 1:
# 遇到運算符的時候，取得堆疊最上面兩個值進行運算
num2 = stack.pop()
num1 = stack.pop()
if value == '+':
stack.append(num1 + num2)
elif value == '-':
stack.append(num1 - num2)
elif value == '*':
stack.append(num1 * num2)
elif value == '/':
# 題目要求除法取整數就好
stack.append(int(num1 / num2))
return stack[-1]
結果
