Evaluate Reverse Polish Notation

MEDIUM

Description

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 <= 10⁴
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Approaches

Checkout 3 different approaches to solve Evaluate Reverse Polish Notation. Click on different approaches to view the approach and algorithm in detail.

Recursive Evaluation

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 tokens array.
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.

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 Analysis

Time Complexity: O(N)Space Complexity: O(N)

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Evaluate Reverse Polish Notation. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Evaluate Reverse Polish Notation

Patterns:

Math

Data Structures:

ArrayStack

Companies:

LinkedIn |Yandex |Citadel |Odoo |