Regex Engine With Groups

Regular expressions are small programs that describe text. Build the core of an engine for them: write full_match(pattern, text) that returns True if pattern matches the whole of text, and False otherwise. Write the matcher yourself rather than using the re module.

The pattern language:

• A lowercase letter or a digit matches that same character.
• . matches any one character.
• * after an item means zero or more copies of it, + means one or more, and ? means zero or one. An item is a letter, a digit, . or a group in parentheses.
• Parentheses make a group, so (ab)+ matches "ab", "abab", "ababab" and so on.
• | separates alternatives, and the pattern matches if any alternative does. It binds more loosely than anything else, so ab|cd means "ab" or "cd", and inside a group it only splits that group. An alternative may be empty: (a|) matches "a" or nothing.

Examples

full_match('colou?r', 'color')      # returns True
full_match('(ab|cd)*e', 'abcdabe')  # returns True
full_match('a(b|c)+d', 'ad')        # returns False
full_match('h.llo|bye', 'hallo')    # returns True

Constraints

• pattern has at most 100 characters and is always valid: parentheses are balanced, and *, + and ? always follow a letter, a digit, . or ), never another *, + or ?. The pattern may be empty, and then it matches only empty text.
• text has at most 100 characters, all lowercase letters and digits.
• Some patterns make a matcher that tries one way after another take far too long, such as (a|aa)*b against a long run of the letter a.