Evaluate Reverse Polish Notation

Medium

The problem

In Reverse Polish Notation the operator comes AFTER the two numbers it works on, so "3 4 +" means 3 + 4. Given a list of tokens (numbers written as strings, and the operators "+", "-", "*", "/"), return the value of the expression. Division throws away the decimal part (it rounds toward zero).

Example 1
Input: tokens = ["8", "3", "-", "2", "*"]
Output: 10
8 - 3 = 5, then 5 × 2 = 10.
Example 2
Input: tokens = ["7", "-2", "/"]
Output: -3
7 / -2 is -3.5, and rounding toward zero gives -3.
Example 3
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
13 / 5 = 2 (decimal part dropped), then 4 + 2 = 6.

Limits

1 ≤ tokens.length ≤ 10,000
The expression is always valid and never divides by zero
Every step and the final result fit in a 32-bit integer

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

In "3 4 +" the operator comes after its operands. Where would you keep the operands waiting?

The idea

Push numbers; on an operator pop two (careful: the first popped is the RIGHT operand), apply it, push the result.

Target: O(n) time, O(n) space

Go function shape

func evalRPN(tokens []string) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// EvalRPN: "3 4 +" puts the operator AFTER its operands, so operands wait on a stack.
func EvalRPN(tokens []string) int {
	var st Stack[int]
	for _, t := range tokens {
		switch t {
		case "+", "-", "*", "/":
			b, a := st.Pop(), st.Pop() // the FIRST pop is the right-hand operand
			switch t {
			case "+":
				st.Push(a + b)
			case "-":
				st.Push(a - b)
			case "*":
				st.Push(a * b)
			default:
				st.Push(a / b) // Go truncates toward zero, as the problem requires
			}
		default:
			n, _ := strconv.Atoi(t)
			st.Push(n)
		}
	}
	return st.Pop()
}

Read the lesson: Stack Basics