Evaluate Reverse Polish Notation

Question

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

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

Division between two integers should truncate toward zero.

Example

Input: ["3", "4", "+"]

Output: 7

Explanation: 3 + 4 = 7

Input: ["5", "1", "2", "+", "4", "*", "+", "3", "-", "2", "/"]

Output: 7

Explanation:
1 + 2 = 3
3 * 4 = 12
5 + 12 = 17
17 - 3 = 14
14 / 2 = 7

My Notes

Use a stack to evaluate expressions.
Push operands to the stack.
When you find an operator, pop two elements, apply the operation, and push the result back.
Final result will be the only value left in the stack.
Time complexity: O(n), Space complexity: O(n)

package main

import (
    "fmt"
    "strconv"
)

type Stack struct {
    items []int
}

func (s *Stack) Push(item int) {
    s.items = append(s.items, item)
}

func (s *Stack) Pop() int {
    popped := s.items[len(s.items)-1]
    s.items = s.items[:len(s.items)-1]
    return popped
}

func evalRPN(tokens []string) int {

    stack := Stack{}

    for _, ch := range tokens {
        switch ch {
        case "+":
            stack.Push(stack.Pop() + stack.Pop())
        case "-":
            op1 := stack.Pop()
            op2 := stack.Pop()
            stack.Push(op2 - op1)
        case "*":
            stack.Push(stack.Pop() * stack.Pop())
        case "/":
            op1 := stack.Pop()
            op2 := stack.Pop()
            stack.Push(op2 / op1)
        default:
            value, _ := strconv.Atoi(ch)
            stack.Push(value)
        }
    }

    return stack.items[0]
}

func main() {
    result := evalRPN([]string{"5", "1", "2", "+", "4", "*", "+", "3", "-", "2", "/"})
    fmt.Println(result)
}