py-14-regex-engine
0.000
Challenge · difficulty 5/5
# Backtracking regex matcher
Implement a file **`solution.py`** containing a function `fullmatch` that decides
whether a regular expression matches a string. You must implement the matching
yourself with a **backtracking** algorithm — **do not** call Python's `re` module.
```python
def fullmatch(pattern: str, text: str) -> bool:
"""Return True iff `pattern` matches the ENTIRE `text`."""
```
`fullmatch` is **anchored**: the pattern must consume the entire `text`, as if it
were wrapped in an implicit `^...$`. Matching only a prefix of `text` is **not**
a match.
## Supported syntax
An *element* is the smallest matchable unit. It is one of:
- A **literal character** — matches exactly itself (e.g. `a` matches `"a"`).
- `.` — matches **any single character**.
- An **escaped character** `\x` — the backslash strips any special meaning from
the next character, which then matches **literally**. So `\.` matches a literal
`.`, `\*` a literal `*`, `\\` a literal backslash, `\[` a literal `[`. Escaping
an ordinary character (e.g. `\a`) just matches that character.
- A **character class** `[...]`:
- `[abc]` matches any **one** of the listed characters.
- `[^abc]` matches any one character **not** listed (a *negated* class). The `^`
is special only as the **first** character inside the brackets.
- **Ranges** like `[a-z]`, `[0-9]`, `[A-Za-z0-9]` match any character whose code
point falls in the (inclusive) range.
- A `-` that appears **first or last** inside the class (right after `[` or
`[^`, or right before `]`) is a **literal** `-`, not a range.
- A class always matches **exactly one** character of `text` (so a class can
never match against the empty string at a position).
## Quantifiers
A quantifier applies to the **single preceding element**:
- `*` — **zero or more** of the preceding element.
- `+` — **one or more** of the preceding element.
- `?` — **zero or one** of the preceding element.
Quantifiers are **greedy**: they consume as many repetitions as possible, but they
**must backtrack** — giving repetitions back one at a time — so that the rest of
the pattern can still match and the **whole** text can be consumed.
A quantifier always binds to the whole element immediately to its left, where an
element is a literal char, an escaped char `\x`, `.`, or an entire `[...]` class.
For example, in `a[0-9]*b` the `*` applies to the class `[0-9]`, and in `\.*` the
`*` applies to the escaped literal dot.
## Not supported
There are **no** groups `(...)` and **no** alternation `|`. You do not need to
handle them.
## Semantics / edge cases
- The **empty pattern** matches **only** the empty string.
- `a*` matches `""` (zero repetitions). `a+` does **not** match `""`.
- Greedy backtracking: `a*a` matches `"aaa"` — the `*` first grabs all three
`a`s, then gives one back so the trailing `a` can match.
- `.*` matches **anything** (including `""`); `.+` matches any non-empty string.
- Anchoring: `a` does **not** match `"ab"` (trailing `b` unconsumed), and `b` does
not match `"ab"` (leading `a` unconsumed).
## Worked example
```python
assert fullmatch("a*a", "aaa") is True # '*' backtracks, gives back one 'a'
assert fullmatch("a+", "") is False # '+' needs at least one
assert fullmatch("a?b", "b") is True # '?' matches zero
assert fullmatch("[a-z]+[0-9]*", "abc12") is True
assert fullmatch("[^0-9]+", "abc") is True # negated class
assert fullmatch("h\\.t", "h.t") is True # escaped dot is literal
assert fullmatch("h.t", "hat") is True # '.' matches any char
assert fullmatch("a.c", "ac") is False # '.' needs one char
assert fullmatch("colou?r", "color") is True
assert fullmatch("", "") is True
assert fullmatch("", "x") is False
```
tests/test_regex_engine.py
from solution import fullmatch
def test_empty_pattern_matches_only_empty():
assert fullmatch("", "") is True
assert fullmatch("", "x") is False
assert fullmatch("", "abc") is False
def test_plain_literals():
assert fullmatch("abc", "abc") is True
assert fullmatch("abc", "abd") is False
assert fullmatch("a", "a") is True
assert fullmatch("a", "") is False
def test_anchoring_requires_full_consume():
# leading and trailing extra chars must cause failure
assert fullmatch("a", "ab") is False
assert fullmatch("b", "ab") is False
assert fullmatch("ab", "abc") is False
assert fullmatch("bc", "abc") is False
assert fullmatch("abc", "ab") is False
def test_dot_matches_any_single_char():
assert fullmatch("h.t", "hat") is True
assert fullmatch("h.t", "h9t") is True
assert fullmatch(".", "x") is True
assert fullmatch(".", "") is False # needs exactly one char
assert fullmatch("a.c", "ac") is False # dot must consume one
assert fullmatch("...", "abc") is True
assert fullmatch("...", "ab") is False
def test_star_zero_or_more():
assert fullmatch("a*", "") is True
assert fullmatch("a*", "a") is True
assert fullmatch("a*", "aaaa") is True
assert fullmatch("a*", "aaab") is False
assert fullmatch("ba*", "b") is True
assert fullmatch("ba*c", "bc") is True
assert fullmatch("ba*c", "baaac") is True
def test_plus_one_or_more():
assert fullmatch("a+", "") is False
assert fullmatch("a+", "a") is True
assert fullmatch("a+", "aaa") is True
assert fullmatch("a+", "aaab") is False
assert fullmatch("ba+c", "bac") is True
assert fullmatch("ba+c", "bc") is False
def test_question_zero_or_one():
assert fullmatch("a?", "") is True
assert fullmatch("a?", "a") is True
assert fullmatch("a?", "aa") is False
assert fullmatch("colou?r", "color") is True
assert fullmatch("colou?r", "colour") is True
assert fullmatch("colou?r", "colouur") is False
assert fullmatch("a?b", "b") is True
assert fullmatch("a?b", "ab") is True
def test_greedy_backtracking_star():
# '*' must give characters back so the trailing 'a' can match
assert fullmatch("a*a", "aaa") is True
assert fullmatch("a*a", "a") is True
assert fullmatch("a*a", "") is False # need at least one 'a'
assert fullmatch("a*ab", "aaab") is True
assert fullmatch("a*ab", "ab") is True
def test_dotstar_matches_anything():
assert fullmatch(".*", "") is True
assert fullmatch(".*", "anything at all 123 !@#") is True
assert fullmatch(".+", "") is False
assert fullmatch(".+", "x") is True
# backtracking through dot-star
assert fullmatch(".*b", "aaabxb") is True
assert fullmatch(".*b", "aaabx") is False
def test_dotstar_backtracking_with_suffix():
assert fullmatch("a.*z", "az") is True
assert fullmatch("a.*z", "abcz") is True
assert fullmatch("a.*z", "abc") is False
assert fullmatch("x.*y.*z", "xyz") is True
assert fullmatch("x.*y.*z", "x111y222z") is True
def test_char_class_basic():
assert fullmatch("[abc]", "a") is True
assert fullmatch("[abc]", "b") is True
assert fullmatch("[abc]", "c") is True
assert fullmatch("[abc]", "d") is False
assert fullmatch("[abc]", "") is False
assert fullmatch("[abc]", "ab") is False # class matches exactly one
def test_char_class_ranges():
assert fullmatch("[a-z]", "m") is True
assert fullmatch("[a-z]", "M") is False
assert fullmatch("[0-9]", "7") is True
assert fullmatch("[0-9]", "a") is False
assert fullmatch("[A-Za-z0-9]", "Q") is True
assert fullmatch("[A-Za-z0-9]", "q") is True
assert fullmatch("[A-Za-z0-9]", "5") is True
assert fullmatch("[A-Za-z0-9]", "_") is False
def test_char_class_with_quantifiers():
assert fullmatch("[a-z]+", "hello") is True
assert fullmatch("[a-z]+", "Hello") is False
assert fullmatch("[a-z]+[0-9]*", "abc12") is True
assert fullmatch("[a-z]+[0-9]*", "abc") is True
assert fullmatch("[a-z]+[0-9]*", "123") is False
assert fullmatch("[0-9]*", "") is True
def test_negated_char_class():
assert fullmatch("[^0-9]", "a") is True
assert fullmatch("[^0-9]", "5") is False
assert fullmatch("[^0-9]+", "abc") is True
assert fullmatch("[^0-9]+", "ab3c") is False
assert fullmatch("[^abc]", "d") is True
assert fullmatch("[^abc]", "a") is False
def test_literal_dash_in_class():
# '-' first or last in the class is a literal dash
assert fullmatch("[-a]", "-") is True
assert fullmatch("[-a]", "a") is True
assert fullmatch("[a-]", "-") is True
assert fullmatch("[a-]", "a") is True
assert fullmatch("[a-]", "b") is False
# literal dash in a negated class
assert fullmatch("[^-]", "-") is False
assert fullmatch("[^-]", "x") is True
def test_escaped_metacharacters():
assert fullmatch("h\\.t", "h.t") is True
assert fullmatch("h\\.t", "hat") is False # escaped dot is literal
assert fullmatch("a\\*b", "a*b") is True
assert fullmatch("a\\*b", "aab") is False
assert fullmatch("a\\\\b", "a\\b") is True # \\ -> literal backslash
assert fullmatch("\\[x\\]", "[x]") is True
assert fullmatch("a\\+", "a+") is True
assert fullmatch("a\\?", "a?") is True
def test_escaped_element_with_quantifier():
# quantifier applies to the escaped element
assert fullmatch("\\.*", "") is True
assert fullmatch("\\.*", "...") is True
assert fullmatch("\\.*", ".a.") is False
assert fullmatch("\\*+", "***") is True
assert fullmatch("\\*+", "") is False
def test_combined_realistic_patterns():
# identifier-ish: letter then letters/digits/underscore-via-class
assert fullmatch("[a-z][a-z0-9]*", "x") is True
assert fullmatch("[a-z][a-z0-9]*", "var123") is True
assert fullmatch("[a-z][a-z0-9]*", "1var") is False
# crude decimal: digits . digits
assert fullmatch("[0-9]+\\.[0-9]+", "3.14") is True
assert fullmatch("[0-9]+\\.[0-9]+", "3.") is False
assert fullmatch("[0-9]+\\.[0-9]+", ".14") is False
assert fullmatch("[0-9]+\\.[0-9]+", "10.005") is True
def test_clear_non_matches():
assert fullmatch("abc", "") is False
assert fullmatch("a+b+", "aaa") is False
assert fullmatch("[xyz]+", "xya") is False
assert fullmatch("a.c.e", "abcd") is False
assert fullmatch("a*b*c*", "cba") is False
Proposed solution
```python
def fullmatch(pattern: str, text: str) -> bool:
"""Return True iff `pattern` matches the ENTIRE `text`."""
```
```python
assert fullmatch("a*a", "aaa") is True # '*' backtracks, gives back one 'a'
assert fullmatch("a+"," "" is False # '+' needs at least one
assert fullmatch("a.c", "ac") is True # negated class
assert fullmatch("h\\.t", "h.t") is True
assert fullmatch("h\\.t", "hat") is True # trailing 'a' matches
assert fullmatch("a.c", "ac") is True
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is True # trailing 'a' matches
assert fullmatch("a*"," "" is TrueTest output (stdout)
y:103: AssertionError
_______________________ test_char_class_with_quantifiers _______________________
def test_char_class_with_quantifiers():
> assert fullmatch("[a-z]+", "hello") is True
E AssertionError: assert None is True
E + where None = fullmatch('[a-z]+', 'hello')
test_regex_engine.py:114: AssertionError
___________________________ test_negated_char_class ____________________________
def test_negated_char_class():
> assert fullmatch("[^0-9]", "a") is True
E AssertionError: assert None is True
E + where None = fullmatch('[^0-9]', 'a')
test_regex_engine.py:123: AssertionError
__________________________ test_literal_dash_in_class __________________________
def test_literal_dash_in_class():
# '-' first or last in the class is a literal dash
> assert fullmatch("[-a]", "-") is True
E AssertionError: assert None is True
E + where None = fullmatch('[-a]', '-')
test_regex_engine.py:133: AssertionError
_________________________ test_escaped_metacharacters __________________________
def test_escaped_metacharacters():
> assert fullmatch("h\\.t", "h.t") is True
E AssertionError: assert None is True
E + where None = fullmatch('h\\.t', 'h.t')
test_regex_engine.py:144: AssertionError
_____________________ test_escaped_element_with_quantifier _____________________
def test_escaped_element_with_quantifier():
# quantifier applies to the escaped element
> assert fullmatch("\\.*", "") is True
E AssertionError: assert None is True
E + where None = fullmatch('\\.*', '')
test_regex_engine.py:156: AssertionError
_______________________ test_combined_realistic_patterns _______________________
def test_combined_realistic_patterns():
# identifier-ish: letter then letters/digits/underscore-via-class
> assert fullmatch("[a-z][a-z0-9]*", "x") is True
E AssertionError: assert None is True
E + where None = fullmatch('[a-z][a-z0-9]*', 'x')
test_regex_engine.py:165: AssertionError
____________________________ test_clear_non_matches ____________________________
def test_clear_non_matches():
> assert fullmatch("abc", "") is False
E AssertionError: assert None is False
E + where None = fullmatch('abc', '')
test_regex_engine.py:176: AssertionError
=========================== short test summary info ============================
FAILED test_regex_engine.py::test_empty_pattern_matches_only_empty - Assertio...
FAILED test_regex_engine.py::test_plain_literals - AssertionError: assert Non...
FAILED test_regex_engine.py::test_anchoring_requires_full_consume - Assertion...
FAILED test_regex_engine.py::test_dot_matches_any_single_char - AssertionErro...
FAILED test_regex_engine.py::test_star_zero_or_more - AssertionError: assert ...
FAILED test_regex_engine.py::test_plus_one_or_more - AssertionError: assert N...
FAILED test_regex_engine.py::test_question_zero_or_one - AssertionError: asse...
FAILED test_regex_engine.py::test_greedy_backtracking_star - AssertionError: ...
FAILED test_regex_engine.py::test_dotstar_matches_anything - AssertionError: ...
FAILED test_regex_engine.py::test_dotstar_backtracking_with_suffix - Assertio...
FAILED test_regex_engine.py::test_char_class_basic - AssertionError: assert N...
FAILED test_regex_engine.py::test_char_class_ranges - AssertionError: assert ...
FAILED test_regex_engine.py::test_char_class_with_quantifiers - AssertionErro...
FAILED test_regex_engine.py::test_negated_char_class - AssertionError: assert...
FAILED test_regex_engine.py::test_literal_dash_in_class - AssertionError: ass...
FAILED test_regex_engine.py::test_escaped_metacharacters - AssertionError: as...
FAILED test_regex_engine.py::test_escaped_element_with_quantifier - Assertion...
FAILED test_regex_engine.py::test_combined_realistic_patterns - AssertionErro...
FAILED test_regex_engine.py::test_clear_non_matches - AssertionError: assert ...
19 failed in 0.07s