What it is
Parsing problems ask you to interpret a string according to a small grammar — an arithmetic expression, a bracket-encoded repeat scheme, a numeric literal with sign and leading-whitespace rules — without using a built-in evaluator. The technique is to name the grammar's stages explicitly (skip whitespace, read an optional sign, accumulate digits, handle an operator, descend into a nested group) and write one piece of code per stage, rather than trying to handle every case in one pass of ad hoc conditionals. Two structural tools recur constantly: a stack (or explicit save/restore) for anything that nests, and delayed commitment — holding a partially-built number or term until the next token tells you what to do with it.
When it applies
- The input has precedence rules (multiplication before addition) or nesting (parentheses, bracket-repeat groups) that a single left-to-right scan can't resolve without extra state.
- You're told not to use a language's built-in parser or evaluator — that's a signal the interviewer wants to see the state machine, not just the answer.
- The grammar has a small number of well-defined stages that always occur in the same relative order (sign, then digits, then stop) — that's a tell for a hand-rolled stage-by-stage tokenizer rather than a general parsing library.
- It does not apply when the "parsing" is actually a search or DP problem in disguise — don't reach for a state machine when the real question is about optimal substructure or reachability; use it specifically when the task is turning a string into a value or structure according to fixed rules.
Tells in the problem
- "Evaluate this arithmetic expression" with specified operator precedence and no parentheses — a term-stack (or two rolling accumulators) that delays committing a number until the operator after it is known.
- The same, with parentheses added — save the enclosing context (running result and sign) on a stack when entering
(, restore and fold in when the matching)arrives. - "The encoding rule is
k[...]" or similar nested repeat-group syntax — a stack of(prefix so far, repeat count), or an equivalent recursive descent, one level per open bracket. - "Convert this string to an integer following these rules, in order" — a literal stage-by-stage tokenizer (whitespace, sign, digits, stop), where ambiguous inputs are resolved by asking "which stage are we in" rather than pattern-matching the whole string at once.
- Explicit ambiguous or adversarial example inputs in the prompt (
"+-1","2[p3[e]]", ties in operator order) — a strong signal that the grading is about correctly enumerating edge cases, not just handling the common path.
The classic mistake
The recurring bug is committing a number or term too early — adding it to a running total the moment its digits are read, before knowing whether the next character is another digit, an operator that changes its sign, or a *// that needs to fold it into the previous term instead of standing alone. The fix is uniform across every parsing problem here: keep the "current" value (a number, a term, a sub-result) in a holding variable and only commit it into the enclosing structure when you see the token that tells you how it's used — an operator, a closing bracket, or the end of the string. A second common bug is losing state across a nesting boundary — forgetting to save the sign or partial result before descending into a ( or [, so the enclosing context is wrong or lost by the time you return to it.
Questions to start with
- String to Integer (atoi) — the purest stage-by-stage tokenizer, with no nesting, where ambiguous inputs are resolved by naming the current stage.
- Basic Calculator II — the delayed-commitment idea in its cleanest form: a term isn't pushed until the operator after it is known.
- Decode String — nesting without arithmetic precedence: a stack of
(prefix, count)pairs, one level per open bracket. - Basic Calculator — delayed commitment and nesting combined, where entering a parenthesis means saving the enclosing result and sign before starting fresh.