Infix to Postfix in Python

"""Convert an infix expression to postfix (Reverse Polish Notation) using a stack."""

PRECEDENCE = {"^": 3, "*": 2, "/": 2, "%": 2, "+": 1, "-": 1}
RIGHT_ASSOCIATIVE = {"^"}


def tokenize(expression: str) -> list[str]:
    """Split an infix string into operands, operators and brackets.

    Multi-character operands are kept whole, so "rate * 12" gives
    ["rate", "*", "12"] rather than one token per character.
    """
    tokens: list[str] = []
    i = 0
    while i < len(expression):
        char = expression[i]

        if char.isspace():
            i += 1
        elif char.isalnum() or char in "_.":
            start = i
            while i < len(expression) and (expression[i].isalnum() or expression[i] in "_."):
                i += 1
            tokens.append(expression[start:i])
        elif char in PRECEDENCE or char in "()":
            tokens.append(char)
            i += 1
        else:
            raise ValueError(f"invalid character: {char!r}")

    return tokens


def infix_to_postfix(expression: str) -> str:
    """Return the postfix form of an infix expression."""
    output: list[str] = []
    stack: list[str] = []

    for token in tokenize(expression):
        # Order matters: test brackets and operators first, so anything
        # left over is an operand.
        if token == "(":
            stack.append(token)

        elif token == ")":
            while stack and stack[-1] != "(":
                output.append(stack.pop())
            if not stack:
                raise ValueError("unbalanced brackets: an extra ')'")
            stack.pop()                      # discard the matching "("

        elif token in PRECEDENCE:
            while (
                stack
                and stack[-1] != "("
                and (
                    PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                    or (
                        PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                        and token not in RIGHT_ASSOCIATIVE
                    )
                )
            ):
                output.append(stack.pop())
            stack.append(token)

        else:
            output.append(token)

    while stack:
        top = stack.pop()
        if top == "(":
            raise ValueError("unbalanced brackets: a missing ')'")
        output.append(top)

    return " ".join(output)


if __name__ == "__main__":
    expression = input("Enter an infix expression: ")
    try:
        print("Postfix expression:", infix_to_postfix(expression))
    except ValueError as error:
        print("Error:", error)

while (
    stack
    and stack[-1] != "("
    and (
        PRECEDENCE[stack[-1]] > PRECEDENCE[token]
        or (
            PRECEDENCE[stack[-1]] == PRECEDENCE[token]
            and token not in RIGHT_ASSOCIATIVE
        )
    )
):
    output.append(stack.pop())
stack.append(token)

"""Print the stack and the output after every token, the way an exam answer wants it."""

from infix_to_postfix import PRECEDENCE, RIGHT_ASSOCIATIVE, tokenize


def infix_to_postfix_traced(expression: str) -> list[str]:
    """Convert to postfix, printing one table row per token."""
    output: list[str] = []
    stack: list[str] = []

    print(f"{'TOKEN':<8}{'ACTION':<34}{'STACK':<16}OUTPUT")
    print("-" * 78)

    def row(token: str, action: str) -> None:
        print(f"{token:<8}{action:<34}{' '.join(stack) or '-':<16}{' '.join(output) or '-'}")

    for token in tokenize(expression):
        if token == "(":
            stack.append(token)
            row(token, "push as a marker")

        elif token == ")":
            popped = []
            while stack and stack[-1] != "(":
                popped.append(stack.pop())
            output.extend(popped)
            stack.pop()
            row(token, f"pop {', '.join(popped)}, drop the (" if popped else "drop the (")

        elif token in PRECEDENCE:
            popped = []
            while (
                stack
                and stack[-1] != "("
                and (
                    PRECEDENCE[stack[-1]] > PRECEDENCE[token]
                    or (
                        PRECEDENCE[stack[-1]] == PRECEDENCE[token]
                        and token not in RIGHT_ASSOCIATIVE
                    )
                )
            ):
                popped.append(stack.pop())
            output.extend(popped)
            stack.append(token)
            row(token, f"pop {', '.join(popped)}, push {token}" if popped else f"push {token}")

        else:
            output.append(token)
            row(token, "operand, straight to output")

    tail = stack[::-1]
    output.extend(tail)
    stack.clear()
    row("end", f"pop {', '.join(tail)}" if tail else "nothing left")

    return output


if __name__ == "__main__":
    result = infix_to_postfix_traced("A + B * C - (D / E)")
    print("\nPostfix:", " ".join(result))

"""Evaluate a postfix expression with a second stack."""

import operator

from infix_to_postfix import infix_to_postfix

OPERATIONS = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
    "%": operator.mod,
    "^": operator.pow,
}


def evaluate_postfix(postfix: str) -> float:
    """Push operands; on each operator pop two values and push the result."""
    stack: list[float] = []

    for token in postfix.split():
        if token in OPERATIONS:
            if len(stack) < 2:
                raise ValueError(f"not enough operands for '{token}'")
            right = stack.pop()
            left = stack.pop()
            stack.append(OPERATIONS[token](left, right))
        else:
            stack.append(float(token))

    if len(stack) != 1:
        raise ValueError("malformed postfix expression")
    return stack[0]


if __name__ == "__main__":
    for infix in ["2 + 3 * 4", "(2 + 3) * 4", "3 + 4 * 2 / (1 - 5) ^ 2", "2 ^ 3 ^ 2", "100 / 5 / 2"]:
        postfix = infix_to_postfix(infix)
        print(f"{infix:<26} -> {postfix:<24} = {evaluate_postfix(postfix):g}")