0150. Evaluate Reverse Polish Notation

# 150. Evaluate Reverse Polish Notation#

## 题目 #

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

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

``````

Example 2:

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

``````

Example 3:

``````
Input: ["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

``````

## 代码 #

``````
package leetcode

import (
"strconv"
)

func evalRPN(tokens []string) int {
if len(tokens) == 1 {
i, _ := strconv.Atoi(tokens)
return i
}
stack, top := []int{}, 0
for _, v := range tokens {
switch v {
case "+":
{
sum := stack[top-2] + stack[top-1]
stack = stack[:top-2]
stack = append(stack, sum)
top--
}
case "-":
{
sub := stack[top-2] - stack[top-1]
stack = stack[:top-2]
stack = append(stack, sub)
top--
}
case "*":
{
mul := stack[top-2] * stack[top-1]
stack = stack[:top-2]
stack = append(stack, mul)
top--
}
case "/":
{
div := stack[top-2] / stack[top-1]
stack = stack[:top-2]
stack = append(stack, div)
top--
}
default:
{
i, _ := strconv.Atoi(v)
stack = append(stack, i)
top++
}
}
}
return stack
}

``````