# Evaluate Reverse Polish Notation

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.

## Examples

``````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 <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
``````

# Analysis

## What is Reverse Polish Notation.

Reverse Polish Notation 是一種把運算元放在運算子之後的表示式

## 實作需要解決的問題

1 需要判別輸入的值是運算元還是運算子

2 需要把運算元轉成整數(輸入是字串)

3 題目說明這些運算子是針對整數的運算 也就是說 3/4 = 0

4 決定何時做運算

## 思考

operand_2 operand_1 operator

## 實作演算法

step 1: 先檢查輸入 string list tokens 長度是否大於 1

step 2: 如果 長度 == 1 則直接把該值轉為整數回傳

step 3: 如果 長度 > 1

``````       初始化 index = 0, result = 0
``````

step 4: 當 index < tokens 長度時 , 檢查 tokens[index] 是否是運算子

step 5: 如果 tokens[index] 是運算子:

``````        從 stack 中 pop 出兩個運算元

更新result 為 兩個運算元以運算子做計算

把 result 放入 stack
``````

step 6: 如果 tokens[index] 是運算元:

``````         把運算子轉成整數放入 stack
``````

step 7: 更新 index = index +1 , 回到 step 4

step 8: 回傳 result

## 程式碼

```import "strconv"
func evalRPN(tokens []string) int {
// stack store operand
if len(tokens) == 1 {
value, _ := strconv.Atoi(tokens[0])
return value
}
stack := []int{}
result := 0
operators := map[string]int{"+": 0, "-": 1, "*": 2, "/": 3}
for _, input := range tokens {
if opCode, isOp := operators[input]; isOp {
topIdx := len(stack) -1
// pop 2 element
second := stack[topIdx]
first := stack[topIdx-1]
stack = stack[0: topIdx-1]
switch opCode {
case 0:
result = first + second
case 1:
result = first - second
case 2:
result = first * second
default:
result = first / second
}
stack = append(stack, result)
} else {
value, _ := strconv.Atoi(input)
stack = append(stack, value)
}
}
return result
}```

## 困難點

1 需要對 Reverse Polish Notation 有理解

2 需要對於程式語言中 string 轉換成 integer 有理解

View Github