Evaluate Reverse Polish Notation LeetCode [Python Solution]

In this blog post, we will tackle the problem of evaluating reverse Polish notation, a mouthful term for a method of computing arithmetic expressions.

The core operations involved are addition, subtraction, multiplication, and division, with a unique twist: the division between two integers should round towards zero.

We’ll explore the problem, understand how reverse Polish notation (RPN) works, and present both a brute-force and an efficient solution in Python.

We’ll also delve into the time and space complexities, clarify constraints, and examine edge cases.

By the end of this post, you’ll have a solid understanding of how to solve the “Evaluate Reverse Polish Notation” problem.

Problem Overview
You are given an array of strings, tokens, which represents an arithmetic expression in Reverse Polish Notation.

Your task is to evaluate the expression and return an integer that represents its value.

The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’.

Each operand can be an integer or another expression.

Significantly, the division between two integers should always round towards zero, and there will be no division by zero.

It’s assumed that the input represents a valid arithmetic expression in RPN, and both the answer and intermediate calculations can be represented within 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 = 22

Constraints:

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

Now, let’s dive into the problem, of understanding RPN constraints.

Understanding RPN Constraints

Reverse Polish Notation (RPN) is a way to represent arithmetic expressions without the need for parentheses.

It uses postfix notation, where each operator follows its operands.

The RPN expression is evaluated from left to right, and operators are applied to the previous two values.

Here are the key constraints:

1. Operators: The valid operators are ‘+’, ‘-‘, ‘*’, and ‘/’. These operators are applied to the two operands that immediately precede them.
2. Operands: Each operand can be an integer or another RPN expression. When evaluating an operator, it is applied to the two previous values.
3. Division Behavior: The division operator ‘/’ has a unique behavior. It truncates the result towards zero. This means that if the result is a non-integer, it is rounded towards zero. In Python, this can be achieved using the int() function.
4. Valid Expression: It is guaranteed that the input represents a valid arithmetic expression in RPN. There will be no syntax errors or division by zero.

Now that we understand the problem and its constraints, let’s explore a brute-force and an efficient approach to solving it.

Evaluate Reverse Polish Notation LeetCode Problem 150 [Python Solution]

1. Bruteforce Approach

To solve this problem, we can use a stack data structure. The stack will allow us to keep track of the values as we iterate through the RPN expression. Here’s how the brute-force approach works:

1. Initialize an empty stack to hold values.
2. Iterate through each token in the tokens array.
3. For each token, check if it is an operator (‘+’, ‘-‘, ‘*’, ‘/’), or an operand (integer).
4. If it’s an operand, convert it to an integer and push it onto the stack.
5. If it’s an operator, pop the top two values from the stack and apply the operator to them. Then, push the result back onto the stack.
6. Continue this process until you have processed all tokens.
7. The final result will be the only value left on the stack, so return it.

Here’s a Python code implementation of the brute-force approach:

def evalRPN(tokens):
    stack = []
    for char in tokens:
        if char == "+":
            stack.append(stack.pop() + stack.pop())
        elif char == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif char == "*":
            stack.append(stack.pop() * stack.pop())
        elif char == "/":
            a, b = stack.pop(), stack.pop()
            stack.append(int(float(b) / a))
        else:
            stack.append(int(char))
    return stack[0]

This brute-force approach uses a stack to maintain the intermediate values and performs the required operations based on the RPN expression.

It has a time complexity of O(n) and a space complexity of O(n), where n is the length of the tokens array.

2. Efficient Approach

In the efficient approach, we’ll use a stack to keep track of the values, similar to the brute-force approach.

However, we can optimize the code and make it more concise by using a dictionary to map operators to their respective functions.

This eliminates the need for multiple if-else conditions.

Here’s a Python code implementation of the efficient approach:

def evalRPN(self, tokens: List[str]) -> int:
    stack = []
    operators = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(float(a) / b),
    }
    
    for char in tokens:
        if char in operators:
            b, a = stack.pop(), stack.pop()
            operation = operators[char]
            result = operation(a, b)
            stack.append(result)
        else:
            stack.append(int(char))
    
    return stack[0]

This efficient approach provides a more concise and readable solution, using a dictionary to map operators to their respective functions.

It maintains a stack to handle the values and operations.

The time and space complexities remain the same as the brute-force approach, with a time complexity of O(n) and a space complexity of O(n).

Time and Space Complexity

The time complexity of both the brute-force and efficient approaches is O(n), where n is the length of the tokens array.

This is because we iterate through the array once, performing constant-time operations for each token.

The space complexity is also O(n) in both approaches, as we use a stack to store the intermediate values.

In the worst case, the stack can contain all the elements from the tokens array.

Similar Interview Questions

• Generate Parentheses LeetCode Problem
• Group Anagrams LeetCode Problem

Conclusion

This blog post addressed the “Evaluate Reverse Polish Notation” problem, which involves evaluating arithmetic expressions in reverse Polish notation.

We’ve explored the problem, understood the RPN constraints, and presented a brute-force and efficient approach to solving it in Python.

The efficient approach provides a more concise and readable solution by using a dictionary to map operators

to their respective functions.

The time and space complexities for both approaches are O(n), making them efficient solutions for the problem.

If you have any questions, or suggestions, or want to share your thoughts, feel free to comment below.

We hope this guide has been helpful to beginners in understanding and solving the problem.

Question Link

Now, you’re equipped to handle arithmetic expressions in reverse Polish notation with ease!