String Matching & Parsing

String matching & parsing covers pattern matching, text processing, and building simple parsers: regex-style matching, expression evaluation, template engines, prefix search. It's where "looks right but subtly isn't" bites hardest, because edge cases are everywhere.

What it solves

Finding patterns in text (does this word appear, with what prefix), processing text (tokenize, normalize, rank), and evaluating structured text (arithmetic expressions, command languages, templates).

Recognition signals

• "Pattern", "matches", "prefix", "substring", "dictionary"
• "Tokenize", "parse", "evaluate", "expression", "template", "command language"
• Autocomplete / spell-check / word-search style problems
• Input is a string (or many strings) with structure

The approach

• Prefix/pattern search: a trie (prefix tree) is the natural structure for insert + prefix search and autocomplete. For substring matching on large text, hashing or KMP-style linear scanning beats naive O(n·m).
• Parsing: write a recursive descent parser — tokenize first, then one function per grammar rule, with precedence handled by nesting (multiplication inside addition). Regex is for lexing, not for full grammars.
• Expression evaluation: shunting-yard or recursive descent with explicit operator precedence and parentheses.

What to tell the AI

Build a recursive descent parser for arithmetic: tokenize into numbers, +, -, *, /, parentheses; parse with two levels (term = factor ('*'|'/') factor)*, expr = term ('+'|'-') term)*), returning a number. Throw on unexpected tokens or unbalanced parens.

What to verify

• Precedence — the AI often makes 2 + 3 * 4 come out 20. Check that * binds tighter than +.
• Tokenization edges — empty input, whitespace, negative numbers, multi-digit numbers, decimals.
• Escapes and unicode — escape sequences, non-ASCII characters; the AI's naive char handling breaks.
• Trie correctness — end-of-word flags vs. prefix flags confused (prefix search finds words that aren't words).
• Partial matches — "re.match" vs full-match semantics mixed up.
• Recursion depth — deeply nested expressions blow the stack; note it if inputs can be huge.

Worked micro-example

Parse 2+3*4. Tokenize → 2 + 3 * 4. expr calls term: term parses 3, sees *, parses 4 → 12, returns 12. expr adds 2 → 14. The nesting is the precedence: * handled one level down from +. If your parser evaluates left-to-right, you get 20 — the classic bug.

Practice problems

Try these: Spell Checker (trie + edit-distance ranking), Word Container (trie-backed prefix and word search), Gridbot (parsing a command language before pathfinding).