Parse Boolean Rule Expressions

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.

The trick is to split the work into two clean passes. First, tokenize: identifiers, signed integers, strings with only \" and \\ escapes, comparison operators (match two-character ones first), parentheses, and reserved NOT, AND, OR. Any lexical error returns INVALID immediately. Second, parse with precedence climbing or three functions: parseOr calls parseAnd, which calls parseNot, which calls parsePrimary. NOT recurses into itself for right associativity. AND and OR loop for left associativity. The pitfalls: forgetting to check that all tokens were consumed, accepting a comparison without a literal, treating NOT as a valid identifier, and normalizing integers wrongly. Strip the sign and leading zeros, and map negative zero to 0. With nesting up to 1000 and 200000 tokens, watch recursion depth in your language, and enforce the nesting and length limits yourself. If the parser design slips under pressure, StealthCoder is the hedge on the live OA.

If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.