Evaluate a Nested Predicate Expression Tree

Problem Description

Database query engines often represent filter conditions as an Abstract Syntax Tree (AST) of predicates before executing them against candidate documents.

Implement a function evaluate(predicate: dict, document: dict) -> bool that takes a serialized predicate tree and a document, returning True if the document matches the predicate and False otherwise.

Predicate Grammar

A predicate node is represented as a dictionary and can be one of two types:

1. Logical Operator Node:

   • {"$and": [predicate_1, predicate_2, ...]}: Evaluates to True if all sub-predicates evaluate to True. An empty list evaluates to True.
   • {"$or": [predicate_1, predicate_2, ...]}: Evaluates to True if at least one sub-predicate evaluates to True. An empty list evaluates to False.
   • {"$not": predicate}: Evaluates to True if the child predicate evaluates to False, and vice versa.

2. Comparison (Leaf) Node:

   • {"field": str, "op": str, "val": any}
   • field: A string specifying the field name. Nested fields are separated by dot notation (e.g., "user.address.zip").
   • op: One of the following comparison operators:
     • "$eq": Document value equals val.
     • "$ne": Document value does not equal val.
     • "$gt": Document value is strictly greater than val.
     • "$gte": Document value is greater than or equal to val.
     • "$lt": Document value is strictly less than val.
     • "$lte": Document value is less than or equal to val.
     • "$in": Document value is contained in val (where val is a list).

If a field path does not exist in the document, any comparison other than "$ne" evaluates to False. For "$ne", a missing field evaluates to True.

Function Signature

def evaluate(predicate: dict, document: dict) -> bool:
    pass

Examples

Example 1

predicate = {
    "$and": [
        {"field": "age", "op": "$gte", "val": 18},
        {"field": "status", "op": "$eq", "val": "active"}
    ]
}
document = {"name": "Alice", "age": 22, "status": "active"}
# Output: True

Example 2

predicate = {
    "$or": [
        {"field": "user.role", "op": "$in", "val": ["admin", "moderator"]},
        {
            "$not": {
                "field": "user.banned", "op": "$eq", "val": True
            }
        }
    ]
}
document = {"user": {"role": "guest", "banned": False}}
# Output: True (user.role fails $in, but not user.banned is True)

Constraints

• The maximum depth of the predicate tree is 100.
• Field paths only contain alphanumeric characters and dots (.).
• Leaf comparisons ($gt, $gte, $lt, $lte) will only be evaluated against values of compatible, comparable types (e.g., numbers vs. numbers, strings vs. strings).
• Field names and operator keys are well-formed according to the specification above.