Log inSign up
mediumLeetCodeNot Started

Evaluate Reverse Polish Notation

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

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 '+', '-', '*', and '/'. * 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 given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any ambiguous operations. * The answer and all the intermediate operations can be represented in a 32-bit signed integer.

Example 1 · Simple Arithmetic:

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2 · With Division:

Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 4 + 2 = 6

Example 3 · Complex Expression:

Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: Evaluates to ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22

Constraints:

  • 1 <= tokens.length <= 104
  • tokens[i] is either an operator: +, -, *, or /, or an integer in the range [-200, 200].

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the post-order AST traversal structure inherent to Reverse Polish Notation.
  • Correctly distinguish operator order: b is popped first, then a, and we compute a - b or a / b (NOT b - a).
  • Handle truncation toward zero across programming languages (e.g. integer division vs Math.trunc in JS).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • If token is a number, parse and push to operand stack.
  • If token is an operator (+, -, *, /):
  • Pop b = stack.pop() (right operand).
  • Pop a = stack.pop() (left operand).
  • Compute res = apply(op, a, b) and push res.
  • Final result is the single value remaining on the stack.

Connected Patterns:

Basic CalculatorInfix to PostfixSimplify Path

1. Recursive Sub-Expression Reduction

Intuition

Repeatedly find the first operator in tokens, evaluate it with its two immediately preceding numbers, replace all 3 tokens with the result, and repeat until 1 token remains.

Algorithm

  1. Step 1: Loop while tokens.length > 1.
  2. Step 2: Scan for first index i containing an operator (+, -, *, /).
  3. Step 3: Let a = Number(tokens[i - 2]), b = Number(tokens[i - 1]).
  4. Step 4: Compute res = evaluate(tokens[i], a, b).
  5. Step 5: Replace tokens[i-2...i] with res and repeat.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int evalRPN(std::vector<std::string>& tokens) {
8 while (tokens.size() > 1) {
9 for (size_t i = 0; i < tokens.size(); i++) {
10 if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
11 int a = std::stoi(tokens[i - 2]);
12 int b = std::stoi(tokens[i - 1]);
13 int res = 0;
14 if (tokens[i] == "+") res = a + b;
15 else if (tokens[i] == "-") res = a - b;
16 else if (tokens[i] == "*") res = a * b;
17 else if (tokens[i] == "/") res = a / b;
18
19 tokens.erase(tokens.begin() + i - 2, tokens.begin() + i + 1);
20 tokens.insert(tokens.begin() + i - 2, std::to_string(res));
21 break;
22 }
23 }
24 }
25 return std::stoi(tokens[0]);
26 }
27};
28
29int main() {
30 Solution solver;
31 std::vector<std::string> tokens = {"2", "1", "+", "3", "*"};
32 std::cout << "Result: " << solver.evalRPN(tokens) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2) — Repeatedly scans the array to find the first operator, collapses its operands, and splices the array, taking O(N) per operation across O(N) operators.
  • Space complexity: O(N) — O(N) space for intermediate arrays.

Why Brute Force Doesn't Scale:

For 104 tokens, O(N2) creates 108 shifting operations.

Stack approach evaluates 10,000 tokens in ~2ms.

2. Vector Array-Based Stack

Intuition

Avoid costly array splicing by pushing numbers to a pre-allocated vector and popping operands in O(1) from the tail.

Algorithm

  1. Step 1: Allocate a vector of integers st.
  2. Step 2: Loop through each token.
  3. Step 3: If token is operator, pop top two numbers, evaluate, and push result.
  4. Step 4: Else, parse integer and push to vector.
  5. Step 5: Return st.back().
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int evalRPN(std::vector<std::string>& tokens) {
8 std::vector<int> st;
9 for (const std::string& t : tokens) {
10 if (t == "+" || t == "-" || t == "*" || t == "/") {
11 int b = st.back(); st.pop_back();
12 int a = st.back(); st.pop_back();
13 if (t == "+") st.push_back(a + b);
14 else if (t == "-") st.push_back(a - b);
15 else if (t == "*") st.push_back(a * b);
16 else if (t == "/") st.push_back(a / b);
17 } else {
18 st.push_back(std::stoi(t));
19 }
20 }
21 return st.back();
22 }
23};
24
25int main() {
26 Solution solver;
27 std::vector<std::string> tokens = {"4", "13", "5", "/", "+"};
28 std::cout << "Result: " << solver.evalRPN(tokens) << std::endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass over tokens using a vector to emulate a stack.
  • Space complexity: O(N) — O(N) vector space for operands.

3. Optimal Stack with Switch Dispatch

Intuition

A single clean stack structure directly models postfix LIFO semantics with fast switch dispatch for operators and truncated division.

Algorithm

  1. Step 1: Initialize an empty integer stack st.
  2. Step 2: Iterate through each token in tokens.
  3. Step 3: If token is an operator, pop b (right operand) then a (left operand). Apply operation a op b and push the result back onto st.
  4. Step 4: If token is a number, parse and push onto st.
  5. Step 5: Return st.top().

Optimal RPN Stack Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Stack: [2]
Visual state
Values and pointers at this exact step
stack
TOP
2
Push adds to the top · Pop removes from the top
Why this step matters

Stack: [2]

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <stack>
5
6class Solution {
7public:
8 int evalRPN(std::vector<std::string>& tokens) {
9 std::stack<int> st;
10 for (const std::string& token : tokens) {
11 if (token == "+" || token == "-" || token == "*" || token == "/") {
12 int b = st.top(); st.pop();
13 int a = st.top(); st.pop();
14 if (token == "+") st.push(a + b);
15 else if (token == "-") st.push(a - b);
16 else if (token == "*") st.push(a * b);
17 else if (token == "/") st.push(a / b);
18 } else {
19 st.push(std::stoi(token));
20 }
21 }
22 return st.top();
23 }
24};
25
26int main() {
27 Solution solver;
28 std::vector<std::string> tokens = {"2", "1", "+", "3", "*"};
29 std::cout << "Result: " << solver.evalRPN(tokens) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Single O(N) iteration over all tokens with O(1) stack operations.
  • Space complexity: O(N) — O(N) operand stack space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Sub-Expression ReductionO(N^2)O(N)Scan array for first operator and splice in-place.Array splicing and memory reallocations.
2.Vector Array-Based StackO(N)O(N)Fixed array simulating an operand stack with pointer top.None.
3.Optimal Stack with Switch DispatchOptimalO(N)O(N)Standard LIFO operand stack with O(1) operations and truncation towards zero.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Swapping operands: computing b - a or b / a instead of a - b or a / b.

Pitfall 2:

Using Python // on negative numbers (e.g. -3 // 2 == -2 instead of -1).

Pitfall 3:

Not handling negative string numbers (like '-11') in manual digit parsers.

Crucial Edge Cases to Validate:

  • Single element `tokens = ['42']` — Returns 42 without any operators.
  • Negative operands (e.g. `['-11']`) — Handled correctly during parsing.
  • Division truncating toward zero (e.g. `['6', '-132', '/']`) — 6 / -132 is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify operator operand ordering: b = pop(), a = pop(), result is a / b.
  2. Highlight truncation towards zero: explain why int(a / b) in Python and Math.trunc(a / b) in JS are necessary.
  3. State time and space complexity: strictly O(N) time and O(N) auxiliary space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When evaluating - or / in Postfix, what is the correct order of operands?

2.How is division rounding handled in Python vs JavaScript for negative results (e.g. -13 / 5)?

Back to DSA Sheet