150. Evaluate Reverse Polish Notation

At a Glance

Topic: stack
Pattern: Stack evaluation
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Apple
Frequency: High
LeetCode: 150

Problem (one-liner)

Given an array of tokens representing reverse Polish notation (postfix), evaluate the expression to an integer. Operators are + - * / on the prior two operands; division truncates toward zero.

Recognition Cues

Postfix / RPN
"Stack" whenever operator appears
Integer division truncates toward zero (not floor for negatives)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — build tree then traverse — O(n) but unnecessary structure.
Better — explicit stack of operands — O(n) time / O(n) space.
Optimal — same linear scan — this is the standard algorithm.

Optimal Solution

Go

import "strconv"

func evalRPN(tokens []string) int {
	stack := make([]int, 0, len(tokens))
	for _, token := range tokens {
		switch token {
		case "+", "-", "*", "/":
			right := stack[len(stack)-1]
			left := stack[len(stack)-2]
			stack = stack[:len(stack)-2]
			var result int
			switch token {
			case "+":
				result = left + right
			case "-":
				result = left - right
			case "*":
				result = left * right
			case "/":
				result = left / right
			}
			stack = append(stack, result)
		default:
			value, _ := strconv.Atoi(token)
			stack = append(stack, value)
		}
	}
	return stack[0]
}

JavaScript

function evalRPN(tokens) {
	const stack = [];
	for (const token of tokens) {
		if (token === '+' || token === '-' || token === '*' || token === '/') {
			const right = stack.pop();
			const left = stack.pop();
			let result = 0;
			if (token === '+') {
				result = left + right;
			} else if (token === '-') {
				result = left - right;
			} else if (token === '*') {
				result = left * right;
			} else {
				result = (left / right) | 0;
			}
			stack.push(result);
		} else {
			stack.push(Number(token));
		}
	}
	return stack[0];
}