evaluate_reverse_polish_notation.py

from typing import List


class Solution:
    """LeetCode #150 - Evaluate Reverse Polish Notation (Medium)
    https://leetcode.com/problems/evaluate-reverse-polish-notation/

    Evaluate an expression in postfix (Reverse Polish) notation, where the
    operator follows its operands: ["2", "1", "+", "3", "*"] means (2 + 1) * 3.
    """

    @staticmethod
    def _divide(a: int, b: int) -> int:
        """Integer division that truncates toward zero, as the problem requires.

        This is the classic trap here. Python's // rounds *down*:
            -7 // 2  == -4      but the expected answer is -3.
        Computing the magnitude first and re-applying the sign gives the C-style
        truncation the problem asks for.

        The popular shortcut `int(a / b)` also truncates toward zero, but it
        routes through a float and would lose precision on very large operands.
        """
        quotient = abs(a) // abs(b)
        return -quotient if (a < 0) != (b < 0) else quotient

    def evalRPN(self, tokens: List[str]) -> int:
        """Stack evaluation - one pass, no parsing of parentheses needed.

        Key insight: postfix notation is unambiguous precisely because the
        operands of an operator are always the two most recent results. That is
        LIFO order, so a stack evaluates the whole expression in one pass, and
        no precedence rules or brackets are involved at all.

        Order matters when popping: the *second* pop is the left operand, since
        it was pushed first. Getting that backwards silently breaks - and * only.

        Time:  O(n) - one push or one pop-pop-push per token.
        Space: O(n) - the stack, at most the number of operands.
        """
        stack = []

        for token in tokens:
            if token in ("+", "-", "*", "/"):
                right = stack.pop()       # pushed last  -> right operand
                left = stack.pop()        # pushed first -> left operand

                if token == "+":
                    stack.append(left + right)
                elif token == "-":
                    stack.append(left - right)
                elif token == "*":
                    stack.append(left * right)
                else:
                    stack.append(self._divide(left, right))
            else:
                stack.append(int(token))  # int() also handles "-11"

        return stack[-1]                  # a valid expression leaves exactly one value