Dictionary as Abstract Syntax Tree: Evaluating Complex Expressions

Last update on April 10 2025 12:54:09 (UTC/GMT +8 hours)

90. Dictionary-based Expression Evaluator

Write a Python function that evaluates mathematical expressions represented as dictionaries. The expression dictionary should support basic operations (+, -, *, /), variables, and nested expressions.

Solution:

Python Code:

# Define a function to evaluate a mathematical expression represented as a dictionary.
def evaluate_expression(expr, variables):
    """
    Evaluate a mathematical expression represented as a dictionary.
    
    Args:
        expr: Dictionary representing the expression
        variables: Dictionary mapping variable names to values
    
    Returns:
        The result of evaluating the expression
    """
    # Handle constants: If the expression contains a "const" key, return its value directly.
    if "const" in expr:
        return expr["const"]
    
    # Handle variables: If the expression contains a "var" key, look up its value in the variables dictionary.
    if "var" in expr:
        var_name = expr["var"]  # Get the variable name from the expression.
        if var_name not in variables:
            raise ValueError(f"Variable '{var_name}' not defined")  # Raise an error if the variable is undefined.
        return variables[var_name]  # Return the value of the variable.
    
    # Handle operations: If the expression contains an "op" key, evaluate the operation recursively.
    if "op" in expr:
        op = expr["op"]  # Get the operator (e.g., "+", "-", "*", "/").
        left = evaluate_expression(expr["left"], variables)  # Recursively evaluate the left operand.
        right = evaluate_expression(expr["right"], variables)  # Recursively evaluate the right operand.
        
        # Perform the operation based on the operator type.
        if op == "+":
            return left + right  # Addition.
        elif op == "-":
            return left - right  # Subtraction.
        elif op == "*":
            return left * right  # Multiplication.
        elif op == "/":
            if right == 0:
                raise ZeroDivisionError("Division by zero")  # Raise an error for division by zero.
            return left / right  # Division.
        else:
            raise ValueError(f"Unknown operator: {op}")  # Raise an error for unsupported operators.
    
    # If the expression format is invalid, raise an error.
    raise ValueError("Invalid expression format")

# Example expressions
# Define an example expression: x + y * 2
expr1 = {
    'op': '+',  # The operation is addition.
    'left': {'var': 'x'},  # The left operand is the variable 'x'.
    'right': {'op': '*', 'left': {'var': 'y'}, 'right': {'const': 2}}  # The right operand is y * 2.
}

# Define another example expression: (10 / a) - (b * c)
expr2 = {
    'op': '-',  # The operation is subtraction.
    'left': {'op': '/', 'left': {'const': 10}, 'right': {'var': 'a'}},  # The left operand is 10 / a.
    'right': {'op': '*', 'left': {'var': 'b'}, 'right': {'var': 'c'}}  # The right operand is b * c.
}

# Example variable values
# Define variable values for the first expression: x = 5, y = 3
variables1 = {'x': 5, 'y': 3}

# Define variable values for the second expression: a = 2, b = 3, c = 4
variables2 = {'a': 2, 'b': 3, 'c': 4}

# Evaluate expressions
# Evaluate the first expression using the provided variables.
result1 = evaluate_expression(expr1, variables1)

# Evaluate the second expression using the provided variables.
result2 = evaluate_expression(expr2, variables2)

# Print the results of the evaluations.
print(f"Expression 1 result: {result1}")  # Should be 11 (5 + 3*2).
print(f"Expression 2 result: {result2}")  # Should be -7 (10/2 - 3*4).

Output:

Expression 1 result: 11
Expression 2 result: -7.0

Explanation of Each Line:

Function Definition : Defines evaluate_expression, a function to evaluate a mathematical expression represented as a dictionary.
Docstring : Provides a description of the function, its arguments, and its return value.
Handle Constants : Checks if the expression contains a "const" key and returns its value directly.
Handle Variables : Checks if the expression contains a "var" key and retrieves its value from the variables dictionary.
Undefined Variable Check : Raises an error if the variable is not defined in the variables dictionary.
Handle Operations : Checks if the expression contains an "op" key to evaluate mathematical operations.
Get Operator : Retrieves the operator (e.g., "+", "-", "*", "/") from the expression.
Evaluate Left Operand : Recursively evaluates the left operand of the operation.
Evaluate Right Operand : Recursively evaluates the right operand of the operation.
Addition Operation : Performs addition if the operator is "+".
Subtraction Operation : Performs subtraction if the operator is "-".
Multiplication Operation : Performs multiplication if the operator is "*".
Division Operation : Performs division if the operator is "/", with a check for division by zero.
Unknown Operator Error : Raises an error if the operator is not supported.
Invalid Expression Error : Raises an error if the expression does not match any valid format.
Example Expression 1 : Defines an expression x + y * 2 as a nested dictionary.
Example Expression 2 : Defines an expression (10 / a) - (b * c) as a nested dictionary.
Variable Values for Example 1 : Defines variable values for the first expression: x = 5, y = 3.
Variable Values for Example 2 : Defines variable values for the second expression: a = 2, b = 3, c = 4.
Evaluate Expression 1 : Evaluates the first expression using the provided variables.
Evaluate Expression 2 : Evaluates the second expression using the provided variables.
Print Result 1 : Prints the result of the first expression evaluation (5 + 3 * 2 = 11).
Print Result 2 : Prints the result of the second expression evaluation (10 / 2 - 3 * 4 = -7).

Explanation - Dictionary-based Expression Evaluator

Concept: Evaluate mathematical expressions represented as nested dictionaries.
Challenge: Recursively evaluate an expression tree with operations, variables, and constants.
Key Skills:

Recursive tree traversal
Expression evaluation techniques
Pattern matching

Applications:

Building calculators or formula evaluators
Implementing simple programming language interpreters
Creating rule engines or decision systems
Evaluating user-defined formulas in applications

Benefits:

Provides a flexible way to represent and compute expressions
Allows for dynamic expression creation and modification
Separates expression representation from evaluation logic

For more Practice: Solve these Related Problems:

Write a Python function to evaluate a dictionary-based expression that supports logical operators (`AND`, `OR`, `NOT`).
Write a Python function to evaluate a dictionary-based expression while keeping a detailed log of computation steps.
Write a Python function to extend dictionary-based expressions to support lambda functions as operations.
Write a Python function to validate and optimize a dictionary-based expression tree before evaluation.

Python Code Editor:

Previous: Dictionary Serialization with Circular References.
Next: Python Tuple Exercise Home