The problem I'm solving is a more complex version of pairing up opening and closing brackets.
Instead of matching only on ([{}])
, I additionally need to match arbitrary opening sequences of arbitrary length to closing sequences of arbitrary length, such as '('
which is mapped to ')'
.
While only the top-level matches should be returned, the matches should still account for the inner ones. This means that with a simple parenthesis mapping, ((f))
should match only on the first opening bracket and the final closing bracket.
Motivation:
For parsing a grammar in a custom parser, I need to discern between bracket literals, which are surrounded by apostrophes and brackets on the grammar level, which are normal brackets. The goal is to return a list of all top-level matches that are found. A match is represented as a 4-tuple of the range that the opening and closing sequences span.
For a motivating example, evaluating the expression id '(' [FArgs] ')' ['::' FunType] '{' VarDecl* Stmt+ '}'
with a mapping of {'(': ')', '[': ']', '{': '}', "'('": "')'", "'['": "']'", "'{'": "'}'"}
should yield the following list:
[(3, 6, 15, 18), (19, 20, 32, 33), (34, 37, 53, 56)]
My starting point was this code review on checking for balanced brackets in Python , which I adapted to suit the additional requirements:
- Match arbitrary opening and closing sequences of length >= 1
- Collect tuples of the ranges at which the sequences are found.
Armed with Python 3.9, this is my code:
def get_top_level_matching_pairs(expression: str, mapping: dict[str, str]) \
-> list[tuple[int, int, int, int]]:
"""
Returns all top-level matches of opening sequences to closing sequences.
Each match is represented as a 4-tuple of the range that the opening and closing sequences span.
>>>get_top_level_matching_pairs("(a) op (b) cl", {'(': ')', 'op': 'cl'})
[(0, 1, 2, 3), (4, 6, 11, 13)]
"""
def head_starts_with_one_from(match_targets: Union[KeysView[str], ValuesView[str]]) -> Optional[str]:
# Check whether the expression, from index i, starts with one of the provided keys or values.
# Return the first match found, none otherwise.
return next(filter(lambda m: expression.startswith(m, i), match_targets), None)
res = []
queue = [] # functions as a stack to keep track of the opened pairs.
start_index = None
start_match = None
i = 0
while i < len(expression):
if open := head_starts_with_one_from(mapping.keys()):
if start_index is None:
start_index = i
start_match = open
queue.append(mapping[open]) # Store the closing counterpart for easy comparisons
i += len(open)
continue
if close := head_starts_with_one_from(mapping.values()):
try:
if (stack_head := queue.pop()) == close:
if not queue: # This closing token closes a top-level opening sequence, so add the result
res.append((start_index, start_index + len(start_match), i, i + len(close)))
start_index = None
start_match = None
i += len(close)
continue
# raise mismatched opening and closing characters.
except IndexError:
# raise closing sequence without an opening. (uses stack_head variable)
i += 1
return res
My questions:
- Should I put the preconditions in the docstring for the function or should I verify them in the code? The preconditions are: strings in the mapping are not empty and no mapping string can be a subset of another.
- Is the
head_starts_with_one_from
nested function justified as a nested function? It allows for some neat walrus expressions on theif open
andif close
lines. - Is there a better way to iterate over the expression, given that you need to match a varying range (here: 1 or 3 characters) of the expression at once and sometimes skip over part of it?
Of course, additional comments are more than welcome.
expression
is only 10 characters long, and (2) what is the intendedmapping
for the "motivated example" in your discussion (I see only what I interpret as the inputexpression
and expected output). \$\endgroup\$(7, 8, 9, 10)
for the parens in this part of the text:(b)
? Or do bracket pairs never nest inside of other pairs? If nesting is allowed, your code seems to be behaving incorrectly, because it does not find the 4-tuple just noted. Alternatively, if nesting isn't allowed, we don't need all of the complexity of the classic balanced-bracket algorithm; instead, won't a simple greedy approach work? \$\endgroup\$