Prefix Expression With Variables

HardPython

Problem

Tessian policy evaluation may represent arithmetic rules as prefix expressions. Given a valid prefix expression and an inclusive integer range for every variable, return the maximum value the expression can produce.

The expression contains lowercase single-character variables and binary operators +, -, and *. Each variable appears exactly once. Variables are independent, so any allowed value may be selected for each one.

Formal Specification

Implement maximize_expression(expression, ranges).

expression is a non-empty string in prefix notation, with no spaces.
ranges is a dictionary mapping each variable to a two-element list [low, high].
Return the largest integer obtainable by assigning every variable a value in its inclusive range.
Every operator has exactly two operands.

For a subtree, track both its minimum and maximum possible values. This is necessary because subtraction and multiplication may use a subtree's minimum when maximizing a parent expression.

Constraints

1 <= len(expression) <= 2 * 10^4 - 1
The expression contains at most 10^4 variables
-10^9 <= low <= high <= 10^9
Every variable appears exactly once
The expression is valid binary prefix notation

Function Signature

def maximize_expression(expression, ranges):

Formal Specification

Implement maximize_expression(expression, ranges).

expression is a non-empty string in prefix notation, with no spaces.
ranges is a dictionary mapping each variable to a two-element list [low, high].
Return the largest integer obtainable by assigning every variable a value in its inclusive range.
Every operator has exactly two operands.

For a subtree, track both its minimum and maximum possible values. This is necessary because subtraction and multiplication may use a subtree's minimum when maximizing a parent expression.