Transaction Rule Engines And Expression Parsing

What's being tested

These exercises test whether you can turn a small rule language into a reliable execution pipeline: tokenization, parsing, validation, and evaluation. The interviewer is probing whether you preserve precise Boolean semantics—especially left-to-right evaluation, operator precedence, nested parentheses, and short-circuiting—rather than relying on ad hoc string splitting. Stripe cares because transaction and fraud decisions must be deterministic, explainable, safe on malformed input, and efficient under high request volume.

Core knowledge

• Lexing converts input text into tokens such as identifiers, string literals, Boolean literals, comparison operators, AND, OR, and parentheses. Scan left to right and reject unknown characters, unterminated quotes, and malformed operators before evaluation.

• Recursive-descent parsing maps grammar productions directly to functions such as parse_or(), parse_and(), parse_primary(), and parse_comparison(). A standard grammar gives AND higher precedence than OR: expr := or_expr, or_expr := and_expr (OR and_expr)*.

• Abstract syntax trees (ASTs) separate syntax from execution. Represent a comparison as Comparison(field, operator, value) and Boolean composition as Binary(op, left, right); this makes validation, testing, explanation, and later optimization straightforward.

• Operator precedence must be explicit rather than accidental. Parentheses override precedence, so A OR B AND C means A OR (B AND C), while (A OR B) AND C has a different AST and result.

• If the specification says chains are evaluated strictly left to right, implement that semantics directly; do not silently apply conventional precedence. A fold such as result = result AND next_value preserves left associativity, while parentheses require recursive grouping.

• Short-circuit evaluation avoids unnecessary work: false AND X returns false, and true OR X returns true. It also prevents unsafe field access or function calls on branches whose result cannot affect the outcome.

• Type checking distinguishes a missing field, a field with the wrong type, and a valid comparison that evaluates to false. For example, comparing a Boolean is_international with the string "true" should generally be a malformed rule, not an ordinary transaction rejection.

• Separate syntax errors, semantic errors, and business outcomes. An unbalanced parenthesis or unknown field is invalid input; a valid rule whose condition is false is a normal non-match; an ordered rule list may then continue to the next rule.

• For ordered accept/block rules, define precedence and termination explicitly: evaluate in list order, decide whether the first matching rule wins, and state the default when no rule matches. Return both the decision and useful metadata such as rule ID or reason.

• Shunting-yard parsing is a viable alternative for a larger operator set. It converts infix tokens to postfix using an operator stack, typically in $O(n)$ time and $O(n)$ space; recursive descent is usually clearer for a small fixed grammar.

• Use an immutable or controlled evaluation context containing transaction attributes rather than dynamically evaluating arbitrary source code. Never call eval; a rule language must whitelist fields, operators, literals, and any callable functions.

• Complexity is generally $O(T + A)$ per rule expression, where $T$ is token count and $A$ is visited AST size; short-circuiting can reduce evaluation work. Cache parsed ASTs by rule version or canonical text when many transactions reuse the same rules.

Worked example: Build a Transaction Rule Engine with AND/OR Chains and Nested Parentheses

A strong candidate first asks whether operators use conventional precedence or the explicitly stated left-to-right behavior, what fields and types are legal, and whether malformed rules should throw errors or return a structured validation result. They then declare assumptions about quoting, case sensitivity, missing attributes, and the default decision when no rule matches. The answer should be organized around four pillars: a tokenizer, a parser or AST builder, an evaluator with short-circuit semantics, and validation/error handling. For a small grammar, they would likely choose recursive descent with separate functions for grouped expressions, comparisons, AND, and OR. They would test isolated comparisons, empty or malformed input, deeply nested parentheses, mixed operators, missing fields, and expressions where short-circuiting skips an invalid branch. The key design decision to flag is whether to honor ordinary precedence or the prompt's strict left-to-right rule; silently choosing one can produce systematically wrong transaction decisions. They should return a structured result such as {status, decision, error} rather than conflating parser failure with a false predicate. If they had more time, they would add property-based tests comparing the parser and evaluator against a small reference interpreter, plus rule-versioned AST caching.

A second angle

Evaluate Ordered Accept/Block Transaction Rules with AND, OR and Parentheses

Here the central concern shifts from evaluating one expression to composing multiple policies with ordered rule resolution. Clarify whether the first matching accept or block rule wins, whether later rules can override it, and what happens when every rule misses. Keep parsing and evaluation independent from policy selection: each rule produces a match or non-match, then a separate resolver applies ordering and default behavior. This separation makes it easier to attach an audit reason and test precedence without embedding list-order logic inside the expression parser. In a production service, rule versions should be immutable during one decision so a transaction cannot observe a partially updated policy set.

Common pitfalls

Pitfall: Treating malformed input as a normal false result hides configuration defects. Return a distinct error category for unknown fields, invalid literals, and unbalanced parentheses, while reserving false for a valid predicate that does not match.

A tempting implementation uses expression.split("AND") and split("OR"). That breaks quoted values, nested parentheses, repeated whitespace, operator precedence, and field names containing operator-like text; a tokenizer plus grammar is the more reliable answer.

Candidates sometimes describe a parser but never state the language contract. Explicitly name associativity, precedence, supported types, missing-field behavior, default policy behavior, and whether evaluation is fail-closed; those details are where production correctness lives.

Connections

The interviewer may pivot to finite-state machines for parsing, property-based testing for expression equivalence, and versioned configuration rollout for safely deploying rule changes. Stateful fraud authorization processing also connects evaluation to event ordering, idempotency, time windows, and deterministic replay.