Query Parser: Implement a SQL-Like Filter Expression Parser and Evaluator

Question

## Problem Implement a parser that evaluates simple filter expressions against a row (dict). Supported syntax: - Comparisons: `field = 'value'`, `field > number`, `field < number` - Logic: `AND`, `OR`, `NOT` - Parentheses for grouping Given an expression string and a row dict, return `True` if the row satisfies the expression. ```python def evaluate(expression: str, row: dict) -> bool: pass ``` **Example:** ``` row = {"age": 25, "city": "NYC", "score": 88} evaluate("age > 20 AND city = 'NYC'", row) -> True evaluate("score > 90 OR city = 'LA'", row) -> False evaluate("NOT (age < 18)", row) -> True ``` ## Approach Use a recursive-descent parser: 1. Tokenizer: split into tokens (identifiers, operators, literals, parens). 2. Parser: `parse_expr` -> `parse_or` -> `parse_and` -> `parse_not` -> `parse_atom`. 3. Evaluator: each parse node returns a boolean when given the row. ## Follow-ups 1. How would you add support for `LIKE` pattern matching (e.g., `name LIKE 'A%'`)? 2. How would you support nested fields (e.g., `user.address.city = 'NYC'`)? 3. How would you prevent injection-style attacks if expressions come from user input? 4. What is the time complexity of parsing and evaluation as a function of expression length?

Query Parser: Implement a SQL-Like Filter Expression Parser and Evaluator

Question Details

Full Details

Topics

More from Airbnb