Evaluate Reverse Polish Notation

Medium

Asked by:

+2

More companies

84 views

Topics:

Stacks

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of integer values that the operands can take? Can they be negative?
Can the input array ever be empty or null?
Is the input guaranteed to be a valid Reverse Polish Notation expression?
Besides the operators +, -, *, and /, are there any other operators I should handle?
For division, should I perform integer division, and if so, how should I handle division by zero?

Brute Force Solution

Approach

The brute force approach to evaluating Reverse Polish Notation expressions involves directly processing the provided expression step by step. It operates by reading each element and immediately acting upon it, using a simple mechanism to keep track of intermediate results. It's a very literal interpretation of the expression's structure.

Here's how the algorithm would work step-by-step:

Go through the expression from left to right, one element at a time.
If you find a number, remember it for later.
If you find an operator (like +, -, *, or /), take the last two numbers you remembered.
Apply the operator to those two numbers (in the correct order!).
Forget the two numbers you just used and remember the result of the operation instead.
Continue this process until you reach the end of the expression.
The last number you're remembering at the end is the final answer.

Code Implementation

def evaluate_reverse_polish_notation_brute_force(tokens):
    number_stack = []

    for token in tokens:
        if token.isdigit() or (token.startswith('-') and token[1:].isdigit()):
            number_stack.append(int(token))

        else:
            #If it is not a number, we assume it is an operator
            operand_2 = number_stack.pop()
            operand_1 = number_stack.pop()

            if token == '+':
                result = operand_1 + operand_2
            elif token == '-':
                result = operand_1 - operand_2
            elif token == '*':
                result = operand_1 * operand_2
            else:
                # Integer division toward zero
                result = int(operand_1 / operand_2)

            # Store the intermediate result back on the stack.
            number_stack.append(result)

    #The final result is the only thing left on the stack.
    return number_stack[0]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. Inside the loop, arithmetic operations are performed which take constant time. The stack operations (push and pop) also take constant time on average. Therefore, the time complexity is directly proportional to the number of elements in the input array, resulting in O(n) time complexity.

Space Complexity

O(N) – The brute force approach uses a data structure to remember numbers encountered while traversing the expression. In the worst-case scenario, where the expression consists only of numbers, all N elements could be stored. Therefore, the auxiliary space grows linearly with the number of elements in the input. This means the algorithm uses O(N) extra space to store the operands.

Optimal Solution

Approach

This problem involves evaluating a mathematical expression written in a specific format. The optimal approach uses a 'last in, first out' data structure to keep track of numbers and perform operations in the correct order.

Here's how the algorithm would work step-by-step:

Read the expression from left to right, one element at a time.
If the element is a number, put it on top of the stack.
If the element is an operator (like +, -, *, or /), take the top two numbers from the stack.
Perform the operation on the two numbers you took off the stack (remembering that the order matters for subtraction and division).
Put the result of the operation back onto the stack.
Repeat steps 2-5 until you have processed all the elements of the expression.
The final result will be the single number remaining on the stack.

Code Implementation

def evaluate_reverse_polish_notation(tokens):
    number_stack = []

    for token in tokens:
        if token in ('+', '-', '*', '/'):
            # Ensure operations are done in correct order
            operand_2 = number_stack.pop()
            operand_1 = number_stack.pop()

            if token == '+':
                result = operand_1 + operand_2
            elif token == '-':
                result = operand_1 - operand_2
            elif token == '*':
                result = operand_1 * operand_2
            else:
                # Integer division as per problem description
                result = int(operand_1 / operand_2)

            # Push the result back onto the stack
            number_stack.append(result)

        else:
            # Convert string to integer and push onto the stack
            number_stack.append(int(token))

    # The final result is the only item left on the stack
    return number_stack.pop()

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array 'tokens' once. In each iteration, it either pushes a number onto the stack or performs an operation by popping two numbers, performing the operation, and pushing the result back. Each of these stack operations (push and pop) takes constant time O(1). Therefore, the time complexity is determined by the single pass through the input array of size n, leading to a time complexity of O(n).

Space Complexity

O(N) – The algorithm uses a stack to store numbers encountered while processing the Reverse Polish Notation expression. In the worst-case scenario, where the expression contains only numbers and no operators, all N elements of the input will be pushed onto the stack. Therefore, the auxiliary space required for the stack grows linearly with the number of tokens in the input. This leads to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException since there's nothing to evaluate.
Array contains non-string elements	Throw an IllegalArgumentException since only string tokens are expected.
Array contains invalid operators (e.g., '%', '$')	Throw an IllegalArgumentException as these are not valid Reverse Polish Notation operators.
Division by zero	Throw an ArithmeticException or return positive/negative infinity based on the specific problem requirements.
Integer overflow/underflow during calculations	Use a larger data type (like long) or check for overflow/underflow before performing the operation to prevent errors.
Single element array with a non-numeric string	Attempt to convert the string to an integer and throw NumberFormatException if it fails.
Input leads to a non-integer result (division producing a float)	Cast the result to an integer according to the problem specifications (truncation or rounding).
Insufficient operands in the expression	Throw an IllegalArgumentException when encountering an operator without enough preceding operands in the stack.

Null or empty input array

How to Handle:

Return 0 or throw an IllegalArgumentException since there's nothing to evaluate.

Array contains non-string elements

How to Handle:

Throw an IllegalArgumentException since only string tokens are expected.

Array contains invalid operators (e.g., '%', '$')

How to Handle:

Throw an IllegalArgumentException as these are not valid Reverse Polish Notation operators.

Division by zero

How to Handle:

Throw an ArithmeticException or return positive/negative infinity based on the specific problem requirements.

Integer overflow/underflow during calculations

How to Handle:

Use a larger data type (like long) or check for overflow/underflow before performing the operation to prevent errors.

Single element array with a non-numeric string

How to Handle:

Attempt to convert the string to an integer and throw NumberFormatException if it fails.

Input leads to a non-integer result (division producing a float)

How to Handle:

Cast the result to an integer according to the problem specifications (truncation or rounding).

Insufficient operands in the expression

How to Handle:

Throw an IllegalArgumentException when encountering an operator without enough preceding operands in the stack.