Faangprep Logo
Log inStart free
Browse curriculum

Evaluate Reverse Polish Notation

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

MediumSolve on LeetCode

Problem Understanding

The array tokens holds an arithmetic expression written in Reverse Polish Notation, where each operator comes after its two operands. Compute its value and return it as an integer.

Valid Operators: +, -, *, /. Integer division truncates toward zero.

Example:

  • Input: ["2","1","+","3","*"]
  • Logic: ((2 + 1) * 3) = 9
  • Output: 9
  • Input: ["4","13","5","/","+"]
  • Logic: (4 + (13 / 5)) = 6

Algorithm Strategy

RPN is perfectly suited for a Stack.

  1. Initialize an empty stack.
  2. Iterate through each token.
  3. If token is a number, push it to the stack.
  4. If token is an operator:
    • pop the top two elements (say b is top, a is next).
    • Perform a <op> b.
    • push the result back.
  5. Final result is the only element left in the stack.

Interactive Visualization

Visualize how operands wait on the stack until an operator consumes them.

Dry Run

Input: ["4", "13", "5", "/", "+"]

Token Action Stack
4 Push 4 [4]
13 Push 13 [4, 13]
5 Push 5 [4, 13, 5]
/ Pop 5, 13. 13 / 5 = 2. Push 2. [4, 2]
+ Pop 2, 4. 4 + 2 = 6. Push 6. [6]
End Result 6

Edge Cases & Common Mistakes

  • Division Order: a / b vs b / a. Remember: first popped is b (right operand).
  • Truncation: Integer division in Python behaves differently for negatives (-1 // 2 = -1 vs C++ 0). Use int(a / b) to truncate towards zero.

Solution

Stack Logic.

Evaluate Reverse Polish Notation Code
1var evalRPN = function(tokens) {
2    const stack = [];
3    for (const t of tokens) {
4         if (t === '+' || t === '-' || t === '*' || t === '/') {
5             const b = stack.pop();
6             const a = stack.pop();
7             if (t === '+') stack.push(a + b);
8             else if (t === '-') stack.push(a - b);
9             else if (t === '*') stack.push(a * b);
10             else stack.push(Math.trunc(a / b));
11         } else {
12             stack.push(Number(t));
13         }
14    }
15    return stack[0];
16};
Previous

Largest Rectangle in Histogram

Next

Min Stack

The approach, step by step

  1. Push numbers

    Push every number token onto the stack.

  2. Apply operators

    For an operator, pop b then a, and push a op b.

  3. Return the result

    After the last token, the single value on the stack is the result.

Frequently asked questions

How do you evaluate Reverse Polish Notation?

Read tokens left to right. Push each number; for an operator, pop the right operand b, then the left operand a, and push a op b. The one value left is the answer.

Why does the operand order matter?

The first value popped is the right-hand operand. For subtraction and division, a − b and a / b differ from b − a and b / a.

How should division be handled?

LeetCode 150 truncates toward zero, so 7 / -3 is -2. Python needs int(a / b) because // floors toward negative infinity.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description