150. Evaluate Reverse Polish Notation

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 150

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are &#39;+&#39;, &#39;-&#39;, &#39;*&#39;, and &#39;/&#39;.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

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",&quo...

Approach & Solution Steps

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 JS Solution

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];
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.