Evaluate a Boolean Formula AST
Company: Sigmacomputing
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Evaluate a Boolean Formula AST
Evaluate a formula represented as a JSON-compatible abstract syntax tree. A formula can contain Boolean literals, integer literals, Boolean operators, and relational operators.
### Function Signature
```python
def evaluate_formula(formula: dict) -> bool:
...
```
### Node Formats
```text
{"type": "boolean", "value": bool}
{"type": "number", "value": int}
{"type": "binary", "op": "AND" | "OR", "left": node, "right": node}
{"type": "relational", "op": "==" | "<" | ">", "left": node, "right": node}
```
### Evaluation Rules
- `AND` and `OR` convert each operand to Boolean: `0` is false, every other integer is true, and Boolean values are unchanged.
- Relational operators convert Boolean operands to integers (`false` to `0`, `true` to `1`) and leave integer operands unchanged.
- Every operator node evaluates to a Boolean.
- After evaluating the root node, coerce its value to Boolean with the same zero/nonzero rule. Thus a root number `0` returns `false`, while any other root integer returns `true`.
### Examples
```text
Input: {"type": "binary", "op": "OR",
"left": {"type": "boolean", "value": true},
"right": {"type": "boolean", "value": false}}
Output: true
Input: {"type": "relational", "op": "<",
"left": {"type": "number", "value": 1},
"right": {"type": "number", "value": 3}}
Output: true
Input: {"type": "relational", "op": "<",
"left": {"type": "number", "value": 1},
"right": {"type": "boolean", "value": true}}
Output: false
```
### Constraints
- The AST contains at most `200_000` nodes.
- Literal integers are in the signed 64-bit range.
- The input is a well-formed tree using exactly the node formats and operators above.
- Do not mutate the input.
### Clarifications
- Numeric truthiness follows the explicit zero/nonzero rule, including negative numbers.
- `==` compares the numeric forms of its two operands, so `true == 1` is true.
- Implement normal short-circuit behavior for `AND` and `OR`.
- The return value is always the primitive Boolean `true` or `false`, including when the root itself is a literal number.
### Hints
- Separate evaluation from the two small coercion rules.
- If you use recursion, consider what happens on a highly skewed tree.
Quick Answer: Evaluate a JSON-compatible Boolean formula AST containing Boolean and integer literals, AND, OR, and relational operators. Apply the specified numeric coercions and short-circuit rules, avoid recursion limits on skewed trees, and always return a primitive Boolean.
Evaluate a JSON-compatible Boolean formula AST containing Boolean and integer literals, short-circuit AND/OR nodes, and numeric ==, <, and > relational nodes. Coerce the root to a primitive Boolean and avoid recursion-depth failure on skewed trees.
Constraints
- Boolean and number literals use the documented node shapes.
- AND and OR convert integer operands with zero/nonzero truthiness.
- Relational operators convert booleans to 0 or 1.
- AND and OR use normal short-circuit behavior.
- The AST may contain up to 200,000 nodes.
Examples
Input: ({"type": "boolean", "value": True},)
Expected Output: True
Explanation: A Boolean literal returns itself.
Input: ({"type": "number", "value": 0},)
Expected Output: False
Explanation: Root numeric zero coerces to false.
Hints
- Use explicit frames to simulate recursive evaluation.
- Pause a binary node after evaluating its left child.
- For AND/OR, decide whether the right child is needed before pushing it.