Evaluate Reverse Polish Notation
MedPrompt
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) = 9Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6Example 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 <= 104tokens[i]is either an operator:"+","-","*", or"/", or an integer in the range[-200, 200].
Approaches
3 approaches with complexity analysis and trade-offs.
This approach treats the RPN expression as a post-order traversal of an expression tree. We can evaluate it recursively. The last token is the root (the main operator), and its children are the results of recursively evaluating the preceding sub-expressions.
Algorithm
- The main function initiates the recursion starting from the end of the
tokensarray. - A recursive helper function is defined. A global or member variable is used to track the current token index, starting from the last one.
- Base Case: If the token at the current index is a number, parse it and return the value.
- Recursive Step: If the token is an operator:
- Decrement the index and recursively call the helper to evaluate the right operand.
- Decrement the index again and recursively call the helper to evaluate the left operand.
- Perform the operation on the two results.
- Return the final result.
Walkthrough
An RPN expression can be defined recursively. The expression is either a number, or it is two RPN expressions followed by an operator. This structure lends itself to a recursive solution. We can process the tokens from right to left.
- We use a global index, initialized to the last index of the token array.
- A recursive function
evaluate()is called. - Inside
evaluate(), we read the token at the current global index and then decrement the index. - If the token is an operator, we know it needs two operands. Since we are processing from right to left, the next token to be processed will be the end of the right operand's sub-expression. So, we make a recursive call to
evaluate()to get the right operand's value. After that returns, we make another recursive call to get the left operand's value. - If the token is a number, it's a base case; we parse it and return the value.
- The result of the operation is then returned up the call stack.
class Solution { int index; public int evalRPN(String[] tokens) { index = tokens.length - 1; return evaluate(tokens); } private int evaluate(String[] tokens) { String token = tokens[index--]; if (isOperator(token)) { int b = evaluate(tokens); // Evaluate right operand first int a = evaluate(tokens); // Evaluate left operand switch (token) { case "+": return a + b; case "-": return a - b; case "*": return a * b; case "/": return a / b; } } return Integer.parseInt(token); } private boolean isOperator(String s) { return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
An elegant solution that directly maps to the recursive definition of an expression tree.
The code can be very concise.
Cons
Can cause a
StackOverflowErrorfor very long expressions due to deep recursion.Has higher constant overhead due to function calls compared to an iterative solution.
Managing the index state across recursive calls can be less intuitive than a simple loop.
This approach involves repeatedly finding the first operator in the list of tokens, evaluating it with its two preceding operands, and replacing the three tokens with the single result. This process continues until only one token (the final result) remains in the list.
Algorithm
- Convert the input
String[]to a mutable list, likeArrayList<String>. - Loop until the list has only one element:
- Iterate through the list to find the first operator at index
i. - The operands are at indices
i-2andi-1. - Perform the operation.
- Replace the three elements (operand, operand, operator) with the single result.
- Restart the search from the beginning of the modified list.
- Iterate through the list to find the first operator at index
- When the loop terminates, the list will have one element. Parse it to an integer and return.
Walkthrough
The core idea is to simulate the reduction of the expression in-place within a list. We start by converting the input array into a dynamic list structure like an ArrayList to allow for element removal.
- Initialize a loop that runs as long as the expression has not been fully evaluated (i.e., the list size is greater than 1).
- Inside the loop, we search for the first occurrence of an operator.
- Once an operator is found at index
i, we know its operands must be the two preceding elements ati-2andi-1. - We parse these operands, perform the calculation, and then update the list. This involves replacing the element at
i-2with the result and removing the elements ati-1andi. - Because the list's structure has changed, we reset our search pointer to the beginning and repeat the process.
- The loop terminates when the list contains a single element, which is the final answer.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public int evalRPN(String[] tokens) { List<String> tokenList = new ArrayList<>(Arrays.asList(tokens)); while (tokenList.size() > 1) { int i = 0; // Find the first operator while (!isOperator(tokenList.get(i))) { i++; } // Operands are at i-2 and i-1 int b = Integer.parseInt(tokenList.get(i - 1)); int a = Integer.parseInt(tokenList.get(i - 2)); int result = 0; switch (tokenList.get(i)) { case "+": result = a + b; break; case "-": result = a - b; break; case "*": result = a * b; break; case "/": result = a / b; break; } // Replace the three tokens with the result tokenList.set(i - 2, String.valueOf(result)); tokenList.remove(i); tokenList.remove(i - 1); } return Integer.parseInt(tokenList.get(0)); } private boolean isOperator(String s) { return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"); }}Complexity
Time
O(N^2)
Space
O(N)
Trade-offs
Pros
Does not require an explicit auxiliary data structure like a stack.
The reduction process is conceptually straightforward.
Cons
Highly inefficient with a time complexity of O(N^2).
Modifying a list while iterating over it is complex and can be error-prone.
The repeated scanning of the list from the beginning after each reduction is very slow.
This is the canonical and most efficient method for evaluating Reverse Polish Notation. It uses a stack to hold operands. When an operator is encountered, it pops the necessary operands, performs the calculation, and pushes the result back onto the stack.
Algorithm
- Initialize an empty stack of integers.
- Iterate through each token in the input array from left to right.
- If the token is a number, convert it to an integer and push it onto the stack.
- If the token is an operator (
+,-,*,/):- Pop the top element from the stack (second operand
b). - Pop the new top element from the stack (first operand
a). - Perform the operation
a operator b. - Push the result back onto the stack.
- Pop the top element from the stack (second operand
- After the loop, the stack will contain one element. Pop and return this final result.
Walkthrough
Reverse Polish Notation is perfectly suited for evaluation using a stack. The 'last-in, first-out' (LIFO) nature of a stack allows us to store operands and retrieve the most recent ones when an operator appears.
The algorithm proceeds as follows:
- We iterate through the tokens one by one.
- If the current token is a number, we push it onto our stack of integers.
- If the current token is an operator, we know that the top two elements on the stack must be the operands for this operation. We pop them, being careful about the order (the first element popped is the right-hand operand, the second is the left-hand operand).
- We then perform the calculation and push the single numerical result back onto the stack.
- By the end of the token list, the stack will hold a single number: the final result of the entire expression.
import java.util.Stack; class Solution { public int evalRPN(String[] tokens) { Stack<Integer> stack = new Stack<>(); for (String token : tokens) { switch (token) { case "+": stack.push(stack.pop() + stack.pop()); break; case "-": int b = stack.pop(); int a = stack.pop(); stack.push(a - b); break; case "*": stack.push(stack.pop() * stack.pop()); break; case "/": int divisor = stack.pop(); int dividend = stack.pop(); stack.push(dividend / divisor); break; default: stack.push(Integer.parseInt(token)); } } return stack.pop(); }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
Optimal time complexity of O(N).
Simple, intuitive, and easy to implement correctly.
Iterative approach avoids recursion depth limits and potential stack overflow errors.
It is the standard and most widely recognized algorithm for this problem.
Cons
Requires O(N) auxiliary space for the stack.
Solutions
Solution
using System.Collections.Generic ; public class Solution { public int EvalRPN ( string [] tokens ) { var stack = new Stack < int >(); foreach ( var token in tokens ) { switch ( token ) { case "+" : stack . Push ( stack . Pop () + stack . Pop ()); break ; case "-" : stack . Push (- stack . Pop () + stack . Pop ()); break ; case "*" : stack . Push ( stack . Pop () * stack . Pop ()); break ; case "/" : var right = stack . Pop (); stack . Push ( stack . Pop () / right ); break ; default : stack . Push ( int . Parse ( token )); break ; } } return stack . Pop (); } }class Solution {public int evalRPN(String[] tokens) { Deque<Integer> stk = new ArrayDeque<>(); for (String t : tokens) { if (t.length() > 1 || Character.isDigit(t.charAt(0))) { stk.push(Integer.parseInt(t)); } else { int y = stk.pop(); int x = stk.pop(); switch (t) { case "+": stk.push(x + y); break; case "-": stk.push(x - y); break; case "*": stk.push(x * y); break; default: stk.push(x / y); break; } } } return stk.pop(); }}class Solution {public: int evalRPN(vector<string> &tokens) { stack<int> stk; for (auto &t : tokens) { if (t.size() > 1 || isdigit(t[0])) { stk.push(stoi(t)); } else { int y = stk.top(); stk.pop(); int x = stk.top(); stk.pop(); if (t[0] == '+') stk.push(x + y); else if (t[0] == '-') stk.push(x - y); else if (t[0] == '*') stk.push(x * y); else stk.push(x / y); } } return stk.top(); }};class Solution: def evalRPN(self, tokens: List[str]) -> int: nums = [] for t in tokens: if len(t) > 1 or t . isdigit(): nums . append(int(t)) else: if t == "+": nums[- 2] += nums[- 1] elif t == "-": nums[- 2] -= nums[- 1] elif t == "*": nums[- 2] *= nums[- 1] else: nums[- 2] = int(nums[- 2] / nums[- 1]) nums . pop() return nums[0]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.