Max Prefix value evaluation problem

max_prefix.py

from __future__ import annotations

from itertools import product
from typing import Generator

OPERATORS: tuple[str, ...] = ("*", "+", "-", "/")


def iter_variables(
    variables: dict[str, tuple[int]]
) -> Generator[dict[str, int], None, None]:
    return (
        dict(zip(variables.keys(), var_values))
        for var_values in product(*variables.values())
    )


def evaluate_prefix_expr(
    expr: list[str], variable_ns: dict[str, int] = {}
) -> int | None:
    """
    Evaluate a given expression and also take a given namespace into consideration.
    """
    stack = []
    for char in reversed(expr):
        is_operator: bool = char in OPERATORS
        if is_operator:
            try:
                op1: int = stack.pop()
                op2: int = stack.pop()
            except IndexError:
                return None
            result: int = eval(f"{op1}{char}{op2}", variable_ns)
            stack.append(int(result))
        else:
            stack.append(int(char) if char.isdigit() else char)

    return stack[0] if len(stack) == 1 else None


def max_evaluate_expression(
    expr: str, variables: dict[str, tuple[int] | int] = {}
) -> int | None:
    """
    Calculate the maximum value of a given expression; in a brute-force manner.

    >>> max_evaluate_expression('+ 6') is None
    True
    >>> max_evaluate_expression('6')
    6
    >>> max_evaluate_expression('+ 6 * - 4 + 2 3 8 ')
    -2
    >>> max_evaluate_expression('+ 10  20 50') is None
    True
    >>> max_evaluate_expression('* + 1 2 3')
    9
    >>> max_evaluate_expression('* + 2 x y', {'x': 1, 'y': 3})
    9
    >>> max_evaluate_expression('* + 2 x y', {'x': (3, 7), 'y': (1, 9)})
    81
    """
    normalized_expr: list[str] = expr.split()
    # make sure everything is iterable, by converting them into a tuple
    for var_name, var_values in variables.items():
        if isinstance(var_values, int):
            variables[var_name] = (var_values,)
    results: list[int | None] = [
        evaluate_prefix_expr(normalized_expr, variable_ns)
        for variable_ns in iter_variables(variables)
    ]
    return max([r for r in results if isinstance(r, int)], default=None)