Stage 3 of 8v2 · 7070d985

Quantifiers

Parse and execute *, +, and ? with greedy repetition.

Build it in your language

The tester treats your program as a black box: any language works. These are just the most convenient ones for this project.

Greedy Quantifiers: +, *, and ?

Quantifiers control repetition of the preceding atom:

+: One or more times.
*: Zero or more times.
?: Zero or one time.

Mental Model: Greedy Expansion with Backtracking

Greedy quantifiers consume as many characters as possible initially. If subsequent atoms fail, the engine backtracks by relinquishing characters one by one.

Your Goal in this Stage

Support +, *, and ? quantifiers in op: "search".

Input Format

json

{
  "op": "search",
  "pattern": "ab+c?",
  "text": "xxabbbczz"
}

Output Format

json

{
  "matched": true,
  "span": [2, 7]
}

Step-by-Step Implementation Guide

Parse AST: Associate quantifiers with preceding token.
Evaluate with backtracking:
- Maximize repetitions greedily.
- Backtrack on subsequent failure.
Emit output: Print JSON with matched and span.

Acceptance Criteria

✅ Correct greedy semantics for +, *, ?.
✅ Backtracks cleanly to satisfy whole pattern.

Output and errors

Multiline examples are formatted for readability. Emit compact JSON without optional spaces, with properties in the order shown by the output examples, and a final newline. Keep logs off stdout. Tests compare exact text. Invalid inputs use stderr containing error, empty stdout, and exit 1. Valid inputs exit 0. Serialize integer results as JSON integers.