Scale Engineer

Evaluate Reverse Polish Notation

Med
#0150Time: O(N)Space: O(N)9 companies
Patterns
Math
Data structures
ArrayStack
Companies
LinkedInYandexCitadelOdoo

Prompt

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].

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

  1. The main function initiates the recursion starting from the end of the tokens array.
  2. A recursive helper function is defined. A global or member variable is used to track the current token index, starting from the last one.
  3. Base Case: If the token at the current index is a number, parse it and return the value.
  4. 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 StackOverflowError for 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.

Solutions

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 (); } }

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.

← Previous

Previous problem

Next →

Next problem