Evaluate a Formula AST with Variables
Company: Sigmacomputing
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Evaluate a Formula AST with Variables
Extend a Boolean-formula evaluator so the AST may contain variable references. Resolve each variable from a supplied environment, then apply the same Boolean and relational rules as for literal nodes.
### Function Signature
```python
def evaluate_formula_with_variables(
formula: dict,
variables: dict[str, int | bool],
) -> bool:
...
```
### Node Formats
```text
{"type": "boolean", "value": bool}
{"type": "number", "value": int}
{"type": "variable", "name": str}
{"type": "binary", "op": "AND" | "OR", "left": node, "right": node}
{"type": "relational", "op": "==" | "<" | ">", "left": node, "right": node}
```
### Example
```text
Input: formula = {
"type": "binary", "op": "AND",
"left": {"type": "variable", "name": "enabled"},
"right": {
"type": "relational", "op": ">",
"left": {"type": "variable", "name": "retries"},
"right": {"type": "number", "value": 0}
}
}
variables = {"enabled": true, "retries": 2}
Output: true
```
### Constraints
- The AST contains at most `200_000` nodes.
- Variable names are nonempty strings.
- Every environment value is a primitive Boolean or signed 64-bit integer.
- The AST otherwise uses only the documented node forms and operators.
- Do not mutate either input.
### Clarifications
- Raise `ValueError` when a referenced name is absent from `variables`.
- `AND` and `OR` treat integer zero as false and every nonzero integer as true.
- Relational operators map `false` to `0` and `true` to `1` before comparing.
- `AND` and `OR` short-circuit, so a missing variable in an unevaluated branch does not raise an error.
- Repeated variable references read the same immutable input environment.
- After evaluating the root, apply the same zero/nonzero Boolean coercion. A root integer literal or integer-valued root variable therefore returns `false` only when its value is zero.
- The result is always a primitive Boolean.
### Hints
- Keep name lookup at the leaf rather than substituting a second AST.
- Test variables in both evaluated and short-circuited branches.
Quick Answer: Evaluate a Boolean formula AST that also resolves integer or Boolean variables from an immutable environment. Preserve short-circuit behavior so missing names in skipped branches do not fail, while evaluated unknown variables raise the required error.
Evaluate a validated Boolean and relational AST containing boolean literals, integer literals, variables, short-circuit AND/OR nodes, and ==, <, > comparisons. Missing variables raise only when their branch is evaluated; the final result is a primitive Boolean.
Constraints
- The AST contains at most 200,000 nodes.
- Environment values are primitive booleans or signed 64-bit integers.
- AND and OR coerce zero to false and nonzero to true.
- Relational operators compare booleans as zero or one.
- Inputs are not mutated.
Examples
Input: {'formula':{'type':'binary','op':'AND','left':{'type':'variable','name':'enabled'},'right':{'type':'relational','op':'>','left':{'type':'variable','name':'retries'},'right':{'type':'number','value':0}}},'variables':{'enabled':True,'retries':2}}
Expected Output: True
Explanation: The supplied variable and comparison example.
Input: {'formula':{'type':'binary','op':'AND','left':{'type':'boolean','value':False},'right':{'type':'variable','name':'missing'}},'variables':{}}
Expected Output: False
Explanation: A false AND left side suppresses missing-variable lookup.
Hints
- Validate AST shape separately from variable resolution.
- Use an explicit task stack to avoid recursion depth limits.
- Delay the right branch task until the left value proves it is needed.