Skip to main content
Talentd

Evaluate Reverse Polish Notation - Solution & Explanation

MediumArrayMathStack11 min readAsked at: Amazon, Microsoft, Apple +15
Practice this problem

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 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","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 

Constraints:

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

Approach Overview

Problem Overview: You receive an array of tokens representing a mathematical expression in Reverse Polish Notation (postfix form). Evaluate the expression and return the final integer result while handling operators like +, -, *, and /.

Approach 1: Stack-Based Evaluation (O(n) time, O(n) space)

The natural way to evaluate Reverse Polish Notation is with a stack. Iterate through each token in the array. If the token is a number, push it onto the stack. If the token is an operator, pop the top two numbers from the stack, apply the operation in the correct order, and push the result back.

This works because postfix notation guarantees that every operator appears after its operands. The stack always holds intermediate results, and each operation reduces two values into one. Continue processing tokens until the end of the array; the stack's top element is the final result. Every token is processed exactly once, giving O(n) time complexity with O(n) space for the stack.

This problem directly tests your understanding of the stack data structure along with simple arithmetic from math. The tokens themselves are stored in an array, and the algorithm iterates through them sequentially.

Approach 2: Recursive Expression Evaluation (O(n) time, O(n) space)

Another way is to evaluate the expression recursively from the end of the token list. When you encounter an operator, recursively compute the right operand and then the left operand, then apply the operator. Each recursive call resolves a sub-expression and returns its value to the caller.

This approach mirrors how expression trees are evaluated, but it is less common in interviews because recursion makes the implementation harder to reason about and debug. It still processes each token once, resulting in O(n) time complexity, with O(n) space used by the recursion call stack.

Recommended for interviews: The stack-based approach is the expected solution. It directly models how postfix expressions are evaluated and demonstrates strong understanding of stacks and expression parsing. Showing awareness of recursive evaluation helps conceptually, but implementing the stack solution cleanly is what interviewers typically look for.

Approach 1: Stack-Based Evaluation

The stack-based approach is ideal for evaluating Reverse Polish Notation (RPN) expressions because it naturally follows the Last-In-First-Out (LIFO) principle, which aligns with the evaluation order of RPN expressions. The key idea is to iterate through the tokens, pushing operands onto the stack, and handling operators by popping the required number of operands from the stack, performing the operation, and pushing the result back onto the stack.

The program uses an integer array as a stack to evaluate the RPN expression. As it processes each token:

  • If the token is a number, it's converted and pushed onto the stack.
  • If it's an operator, the required numbers are popped from the stack, the operation is performed, and the result is pushed back onto the stack.

The final result is the only element left on the stack.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of tokens.
Space Complexity: O(n) due to stack usage.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Evaluation

Time Complexity: O(n), where n is the number of tokens.
Space Complexity: O(n) due to stack usage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based EvaluationO(n)O(n)Standard and most intuitive solution for postfix expressions
Recursive EvaluationO(n)O(n)Useful when modeling the expression as recursive subproblems
Array as Manual StackO(n)O(n)Optimized implementations where dynamic stack objects are avoided

Video Solution

Evaluate Reverse Polish Notation - Leetcode 150 - Python • NeetCode • 181,778 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Evaluate Reverse Polish Notation easy or hard?
Evaluate Reverse Polish Notation is considered a medium-level problem. The logic becomes straightforward once you recognize that postfix expressions are naturally evaluated with a stack, but careful handling of operand order and integer division is required.
Evaluate Reverse Polish Notation Python/Java solution
Python and Java solutions typically use a stack or list to store intermediate numbers. Iterate through tokens, push numbers, and compute results when operators appear. The implementation stays concise and runs in O(n) time with O(n) auxiliary space.
How to solve Evaluate Reverse Polish Notation in O(n)?
Iterate through the token array and maintain a stack of integers. Push numbers onto the stack. When you encounter an operator, pop two numbers, compute the result, and push it back. After processing all tokens, the stack's top value is the final result, achieving O(n) time complexity.
What is the best approach for Evaluate Reverse Polish Notation?
The best approach uses a stack to process tokens sequentially. Push numbers onto the stack, and when an operator appears, pop the top two values, apply the operation, and push the result back. This method processes each token once and runs in O(n) time with O(n) space.
Is Evaluate Reverse Polish Notation asked at Google/Amazon/Meta?
Evaluate Reverse Polish Notation appears frequently in coding interviews at companies like Amazon, Google, and Meta because it tests stack fundamentals and expression evaluation. It is a classic problem used to assess understanding of data structures and parsing logic.
What data structure is used in Evaluate Reverse Polish Notation?
A stack is the primary data structure used to evaluate Reverse Polish Notation. It stores intermediate operands and ensures operators always combine the most recent values in the correct order.
What is the time complexity of Evaluate Reverse Polish Notation?
The optimal solution runs in O(n) time because each token is processed exactly once. Stack operations like push and pop take constant time, so the total complexity grows linearly with the number of tokens.

Ready to solve this problem?

Practice Evaluate Reverse Polish Notation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Basic Calculator

Next

Expression Add Operators