Katkat
Back

Evaluate a Formula AST with Variables

SigmacomputingSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests tree traversal techniques, recursive evaluation, and the implementation of short-circuit logic in expression trees containing variables.

Problem Statement

Given an Abstract Syntax Tree (AST) representing a Boolean expression and a dictionary representing the environment of variables, evaluate the expression to a boolean value.

The AST nodes consist of:

  • Literal(value): Returns the boolean value.
  • Variable(name): Looks up name in the env. If the variable is missing, raise a KeyError.
  • And(left, right): Logical AND. If left evaluates to False, the right child should not be evaluated.
  • Or(left, right): Logical OR. If left evaluates to True, the right child should not be evaluated.
  • Not(node): Logical NOT.

Function Signature

def evaluate(node, env):
    # node: The root of the AST
    # env: A dictionary mapping string names to boolean values
    # Returns: boolean

Constraints

  • The tree can be deeply nested.
  • env is immutable during evaluation.
  • Accessing a variable in a branch that is "short-circuited" should NOT raise a KeyError.

Examples

Example 1:

  • Tree: And(Literal(False), Variable('unknown'))
  • Env: {}
  • Result: False (Short-circuiting prevents KeyError on 'unknown')

Example 2:

  • Tree: Or(Literal(True), Variable('unknown'))
  • Env: {}
  • Result: True

Example 3:

  • Tree: Not(Variable('x'))
  • Env: {'x': True}
  • Result: False

Hints

Hint 1

Use a recursive helper function to perform a post-order traversal or evaluate nodes as needed.

Hint 2

For the 'And' node, evaluate the left child first; only evaluate the right child if the left child is true.

Hint 3

For the 'Or' node, evaluate the left child first; only evaluate the right child if the left child is false.

Follow-up questions

  • How would you extend this to handle integer variables and comparison operators like 'Greater Than'?
  • What changes are needed if the environment can be updated during the evaluation (e.g., assignment expressions)?
  • How would you optimize the AST evaluation if the same expression subtree is evaluated multiple times against different environments?