PythonHaven | Evaluating Reverse Polish Notation

Evaluating Reverse Polish Notation (RPN) in Python

Evaluating Reverse Polish Notation (RPN) is a common problem in computer science, especially in parsing and computation tasks.

As an experienced software engineer, I will walk you through how to solve this problem using Python.

I will start with a basic implementation and then optimize it for better efficiency and readability.

Understanding the Basic Approach

Instead of using parentheses to indicate operation precedence, RPN relies on the order of operations.

Initial Implementation

Below is a straightforward implementation of an RPN evaluator:

from typing import List

class Solution:

    def evalRPN(self, tokens: List[str]) -> int:
        """
        Evaluates a Reverse Polish Notation (RPN) expression.

        The expression is given as a list of string tokens, where each token
        is either an operand (integer) or an operator ('+', '-', '*', '/').
        The division is an integer division, truncating toward zero.

        Args:
            tokens (List[str]): A list of strings representing the RPN expression.

        Returns:
            int: The result of the evaluated expression.

        Example:
            >>> sol = Solution()
            >>> sol.evalRPN(["2", "1", "+", "3", "*"])
            9
            >>> sol.evalRPN(["4", "13", "5", "/", "+"])
            6
            >>> sol.evalRPN(["10", "6", "9", "3", "/", "-", "*"])
            30

        """
        stack = []

        for c in tokens:
            if c in {"+", "-", "*", "/"}:
                a = stack.pop()
                b = stack.pop()
                if c == "+":
                    stack.append(b + a)
                elif c == "-":
                    stack.append(b - a)
                elif c == "*":
                    stack.append(b * a)
                elif c == "/":
                    # Ensure truncation toward zero
                    stack.append(int(float(b) / a))
            else:
                stack.append(int(c))

        return stack[0]

Tim & Space Complexity

Time Complexity
O(n) — Each token is processed once.

Space Complexity
O(n) — Stack stores at most n/2 intermediate results.

Code explanation

Stack keeps track of operands.
When encountering an operator (+, -, *, /), we pop the last two numbers from the stack.
Perform the operation & results pushed to the stack.
Continue until we process all tokens, leaving the final result at the top of the stack.

Issues with the Initial Approach

Repeated pop operations – Each operation pops twice, which could be optimized.
Explicit type casting in division – Using float() is unnecessary when using integer division.
Redundant checks – A more structured approach can make the logic cleaner.

Optimized Version

Now, let's improve the implementation to make it more efficient and readable:

from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        """
        Evaluate the RPN value of an arithmetic e.xpression

        Supported operators are '+', '-', '*', and '/'. Each operand may be an integer,
        and division truncates toward zero (i.e., integer division behavior).

        Args:
            tokens (List[str]): A list of strings representing the RPN expression.

        Returns:
            int: The result of the evaluated expression.

        Example:
            >>> sol = Solution()
            >>> sol.evalRPN(["2", "1", "+", "3", "*"])
            9
            >>> sol.evalRPN(["4", "13", "5", "/", "+"])
            6
            >>> sol.evalRPN(["10", "6", "9", "3", "/", "-", "*"])
            30      
        """
        stack = []
        operators = {
            "+": lambda a, b: b + a,
            "-": lambda a, b: b - a,
            "*": lambda a, b: b * a,
            "/": lambda a, b: int(b / a),
        }
        
        for token in tokens:
            if token in operators:
                a, b = stack.pop(), stack.pop()
                stack.append(operators[token](a, b))
            else:
                stack.append(int(token))
        
        return stack[0]

Time & Space Complexity

Time Complexity
O(n), with n representing the number of tokens in the input list.
Each token is processed once.

Space Complexity
O(n), due to using a stack to store intermediate values.

Improvements in the Optimized Code

Dictionary-based operator handling: Removes multiple if-elif conditions.
Cleaner code structure: Operator functions make the logic clearer.
Efficient division handling: Removes unnecessary float() conversion.

Where to Go from Here

Now that you understand both the initial and optimized versions of the RPN evaluator, try implementing additional operations like exponentiation (^) or modulo (%).

Understanding how stacks work will help in many computing tasks, such as parsing expressions and evaluating formulas.

Need more insights on algorithm optimizations? Stay tuned for upcoming posts on efficient data structures and performance improvements!

Evaluating Reverse Polish Notation