Evaluate Symbol Expressions

Problem Statement

You are building a lightweight formula engine. You are given a dictionary expressions where each key is a variable name (a string of alphanumeric characters) and each value is an arithmetic expression as a string.

An expression is composed of:

• Non-negative integer literals (e.g., "42")
• Variable names referencing other keys in the dictionary
• Binary operators: +, -, and *
• Spaces separating tokens

Your task is to write a function evaluate_expressions(expressions: dict[str, str]) -> dict[str, int] that returns a dictionary mapping each variable name to its fully evaluated integer value.

Requirements

1. Operator Precedence: Standard arithmetic precedence applies (* has higher precedence than + and -). Operations with equal precedence evaluate from left to right.
2. Dependency Resolution: A variable may reference other variables. Dependencies must be evaluated dynamically or resolved in topological order.
3. Error Handling:
   • If an expression references a variable not defined in expressions, raise a ValueError("Undefined variable: ").
   • If there is a circular dependency (e.g., A depends on B and B depends on A), raise a ValueError("Circular dependency detected").

Function Signature

def evaluate_expressions(expressions: dict[str, str]) -> dict[str, int]:
    pass

Examples

Example 1:

expressions = {
    "A": "3 + 2",
    "B": "A * 4",
    "C": "B - 2 + A"
}
output = evaluate_expressions(expressions)
# Output:
# {
#     "A": 5,
#     "B": 20,
#     "C": 23
# }

Explanation: A evaluates to 5. B evaluates to 5 * 4 = 20. C evaluates to 20 - 2 + 5 = 23.

Example 2:

expressions = {
    "x": "y + 1",
    "y": "x * 2"
}
# Raises ValueError("Circular dependency detected")

Example 3:

expressions = {
    "total": "base_price + tax",
    "base_price": "100"
}
# Raises ValueError("Undefined variable: tax")

Constraints

• 1 <= len(expressions) <= 10^4
• Each variable name consists of lowercase and uppercase letters, digits, and underscores.
• Expression length is between 1 and 200 characters.
• Operands and operators in expression strings are guaranteed to be separated by single spaces.
• Values will not exceed standard 64-bit integer limits during evaluation.