Design a Data-Driven Expense Rule Evaluator

Scenario

Modern workforce platforms allow company administrators to configure custom expense approval and compliance policies (for example: "Flag any meal over $75 without a receipt" or "Require secondary approval for flights booked within 7 days of departure").

Your task is to design a rule evaluation engine where policies are stored and configured as JSON documents, evaluated dynamically against submitted expense claims.

Core Requirements

1. Rule Schema: Define a validated JSON schema representing policy conditions and actions. Support basic boolean composition (AND, OR, NOT) and field-level predicates (e.g., eq, gt, in, contains).
2. Engine Architecture & API: Define the core classes and evaluation interface (e.g., PolicyEvaluator.evaluate(expense: dict, policy: Policy) -> EvaluationResult). Specify how conditions are parsed into an executable Abstract Syntax Tree (AST) or composite pattern.
3. Result Contract: The engine must return whether the expense passed, along with specific violated rule IDs and human-readable explanation messages for end users.

Example Rule Definition

{
  "policy_id": "pol_meals_receipt",
  "name": "Meal Receipt Requirement",
  "condition": {
    "operator": "AND",
    "rules": [
      {"field": "category", "op": "EQ", "value": "MEALS"},
      {"field": "amount", "op": "GT", "value": 75.00},
      {"field": "has_receipt", "op": "EQ", "value": false}
    ]
  },
  "action": {
    "type": "FLAG_VIOLATION",
    "severity": "BLOCKING",
    "message": "Meals exceeding $75 require an itemized receipt."
  }
}

Key Considerations to Address

• Invariants & Safety: How do you prevent unsafe execution, infinite recursion in nested rules, or type mismatches (e.g., string comparisons on currency amounts)?
• Missing/Null Fields: How should the engine evaluate conditions referencing attributes that are absent from the submitted expense payload?
• Testing Strategy: How would you test individual operators, compound trees, and schema validation independently?
• Operational Trade-offs: Discuss pre-compiling/caching rule ASTs in memory versus parsing raw JSON per evaluation request.