LeetCode Link: 150. Evaluate Reverse Polish Notation

Problem Definition

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

A Note About Expression Notation

The expressions we're used to seeing are infix expressions, as they match our natural way of thinking. However, infix expressions aren't very computer-friendly.

Take the infix expression 4 + 13 / 5 for example. When a computer scans this from left to right, it reaches 13 and needs to:

  1. Check what operator follows 13
  2. Compare operator precedence
  3. Perform the division with 5
  4. Then backtrack to position 4 to do the addition

Quite cumbersome, isn't it?

However, when we convert this to postfix (RPN) notation: ["4", "13", "5", "/", "+"], everything changes. The computer can process this sequentially using a stack, without worrying about operator precedence or backtracking. This makes postfix notation extremely computer-friendly.

This problem not only serves as an excellent coding exercise but also demonstrates how computers "think" differently from humans.

Thought Process

What is Reverse Polish Notation (RPN)?

RPN is a mathematical notation where the operators follow their operands (also called postfix notation). For example:

  • Infix: (1 + 2) * (3 + 4)
  • RPN: 1 2 + 3 4 + *

Advantages of RPN:

  1. Eliminates the need for parentheses, making expressions unambiguous.
  2. Facilitates computation using a stack: operands are pushed onto the stack, and operators pop the required operands for evaluation.

Approach to Solve the Problem

  1. Use a stack to evaluate the RPN:
    • Push operands onto the stack.
    • When encountering an operator, pop the top two operands from the stack, apply the operator, and push the result back onto the stack.
  2. Division is special:
    • Integer division truncates toward zero, which differs slightly from the behavior of Python’s division operator /. To ensure correctness, implement a custom division function that handles truncation.

Solutions

Using Explicit Operations

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        for token in tokens:
            if token not in ['+', '-', '*', '/']:  # Push operand onto the stack
                stack.append(int(token))
            else:  # Apply the operator to the top two operands
                op2 = stack.pop()
                op1 = stack.pop()
                if token == '+':
                    stack.append(op1 + op2)
                elif token == '-':
                    stack.append(op1 - op2)
                elif token == '*':
                    stack.append(op1 * op2)
                elif token == '/':  # Integer division truncating toward zero
                    stack.append(int(op1 / op2))
        return stack.pop()

Using operator Module for Clean Code

This method uses Python's built-in operator module to map operators (+, -, *, /) to their corresponding functions. A custom div function handles integer division to ensure truncation toward zero.

from operator import add, sub, mul

def div(x, y):
    # Custom integer division with truncation toward zero
    return int(x / y) if x * y > 0 else -(abs(x) // abs(y))

class Solution:
    op_map = {'+': add, '-': sub, '*': mul, '/': div}
    
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        for token in tokens:
            if token not in self.op_map:  # If it's an operand, push onto the stack
                stack.append(int(token))
            else:  # It's an operator, apply it to the top two operands
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1, op2))
        return stack.pop()

Using Python’s eval() function can simplify the implementation but introduces performance and security concerns. Only use this method in controlled environments.

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        for token in tokens:
            if token.lstrip('-').isdigit():  # Check if token is a number
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(eval(f"{op1}{token}{op2}"))
        return stack.pop()

Main reasons why eval() is not recommended:

Security: eval() can execute arbitrary Python code, which could be dangerous if the input isn't trusted

# Seemingly harmless eval:
eval("4+3")  # Works fine

# But eval can execute ANY Python code:
eval("__import__('os').system('rm -rf /')") # Could delete system files
eval("__import__('subprocess').run(['malicious_command'])") # Could run malware
eval("open('passwords.txt', 'r').read()") # Could read sensitive files

In the above solution, while the input tokens are controlled, it's generally considered bad practice to use eval() because:

  • If the input validation (token.lstrip('-').isdigit()) fails
  • If the code is reused in another context where input isn't as controlled
  • If future modifications accidentally weaken the input validation

Performance: It's slower than direct arithmetic operations

Clarity: It makes the code less explicit about what operations are being performed

Complexity Analysis

Time Complexity: O(n)

  • We iterate through each token exactly once
  • Each stack operation (push/pop) takes O(1) time
  • Each arithmetic operation takes O(1) time
  • Total time is linear with respect to the input length

Space Complexity: O(n)

  • In the worst case, we might need to store all operands on the stack
  • For example, with input like ["1", "2", "3", "4", "+", "+", "+"]
  • Maximum stack size will be proportional to number of operands
  • Additional space used by variables is constant O(1)

Key Takeaways

  1. Stack-Based Computation: RPN expressions are naturally suited for stacks. Each operator processes the last two operands, which matches the stack's LIFO nature.
  2. Integer Division: Ensure you handle division correctly with truncation toward zero, as Python’s / operator may not behave as expected.
  3. RPN in Real Life: Reverse Polish Notation was popular in early calculators (like HP models) and remains an efficient way for computers to evaluate expressions.