DAY 26
0
Software Development

# 原始題目

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
``````

# 解題過程

1. 遍歷傳入的 Input，如果值不是運算符代表他是要運算的數字。轉換成 int 存進堆疊裡
2. 遇到運算符號的時候，把堆疊最上面的兩個值取出進行運算( 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]
``````