How should I practice Parse Boolean Rule Expressions?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Stripe phone screen problems in FastPrep.

Is Parse Boolean Rule Expressions associated with Stripe?

FastPrep tags this as a Stripe phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Parsing

Parse Boolean Rule Expressions

Learn this problem

● Hard

StripeFULLTIMEPHONE SCREEN

See Stripe hiring insights

Problem statement

Given one string rule, parse it as a Boolean rule expression. Return a canonical prefix serialization of its abstract syntax tree, or return INVALID when the complete input is malformed.

Tokens

An identifier starts with an ASCII letter or underscore and continues with ASCII letters, digits, or underscores. The uppercase words NOT, AND, and OR are reserved.
An integer literal has an optional + or - followed by one or more decimal digits.
A string literal is enclosed in double quotes and contains printable ASCII characters. Inside a string, \" represents a quote and \\ represents a backslash; no other escape is valid.
The comparison operators are ==, !=, <, <=, >, and >=.
Spaces, tabs, carriage returns, and newlines outside strings are insignificant. Keywords are case-sensitive.

Grammar and precedence

Every comparison has exactly the form identifier comparison-operator literal, where the literal is an integer or string. Comparisons and parenthesized expressions are operands for the Boolean operators.

NOT has the highest Boolean precedence and associates to the right, so repeated NOT operators are allowed.
AND has the next precedence and associates to the left.
OR has the lowest precedence and associates to the left.
Parentheses may override precedence and may be nested.

Canonical serialization

A comparison becomes (operator identifier literal).
A negation becomes (NOT expression).
A conjunction or disjunction becomes (AND left right) or (OR left right).
Integer literals omit a leading + and leading zeros; every zero, including negative zero, becomes 0.
String literals remain quoted and use only \" and \\ escapes in the result.

A lexical error, an incomplete comparison, an unexpected token, an empty expression, or mismatched parentheses makes the complete result INVALID.

Function

parseRuleExpression(rule: String) → String

Examples

Example 1

rule = "age >= 18 AND country == \"US\""return = "(AND (>= age 18) (== country \"US\"))"

Each comparison is serialized first. Because AND joins the two comparison nodes, it becomes the root.

Example 2

rule = "NOT (status == \"blocked\" OR retries > +003)"return = "(NOT (OR (== status \"blocked\") (> retries 3)))"

The parentheses make OR the child of NOT. The signed integer +003 is canonically written as 3.

Example 3

rule = "age >= AND active == 1"return = "INVALID"

The first comparison has no literal after >=, so the complete expression is malformed.

Constraints

The input is an ASCII string and contains at most 200000 tokens.
Parenthesis nesting is at most 1000.
Every identifier and every decoded string literal has length at most 100.
Inputs that violate the token, nesting, or token-length rules return INVALID.