DEV Community

Pavel Morava
Pavel Morava

Posted on

Matching brackets - commented code

If you need to find matching pairs of brackets or anything, you may find this useful.

The task requires us to evaluate whether the examined string contains only matching pairs of bracket.

For instance:

"{ something }" => True # {}
"{ something ]" => False # {]
Enter fullscreen mode Exit fullscreen mode

See more examples in the test section below.

Solution


# One can use list
# but cool kids use double-linked list
# to show themselves :)
# A single linked list would be fine,
# but I am too lazy to implement it
from collections import deque
from typing import Deque, Set

# optimisation
# use set because something in set is O(1)
# something in list is O(n)
PAIRS = {"{}", "()", "[]"}

# zip helps to split pairs, note the asterisk
# again, mapped to set


def check_brackets(text: str, pairs: Set[str] = PAIRS) -> bool:
    OPENING, CLOSING = map(set, zip(*PAIRS))
    history: Deque[str] = deque()
    # traversing all characters
    for character in text:
        if character in OPENING:
            history.append(character)
        elif character in CLOSING:
            try:
                # Popping out of empty list is not a good idea
                # so we need catch a possible error
                last: str = history.pop()
            except IndexError:
                # I could use None
                # but empty string evaluates to False as well.
                # At least I do not need to change type to Optional
                last = ""
            if not last or f"{last}{character}" not in PAIRS:
                # If there is no matching opening bracket,
                # we do not need to continue further
                return False
    # If history is all matched, it is OK
    # If there is something left, we are not OK
    # not [] evaluates to True while not [something] to False
    # This is Python specific behaviour.
    return not history



Enter fullscreen mode Exit fullscreen mode

Tests

# Simple testing
assert check_brackets("{hello}") == True, "Simple"
assert check_brackets("{hello)") == False, "Mismatched"
assert check_brackets("hello}") == False, "Missing"
assert check_brackets("hello}world{") == False, "Missing plus one"
assert check_brackets("(hello{})") == True, "Nested"
assert check_brackets("(hello{(})") == False, "Missing nested"


Enter fullscreen mode Exit fullscreen mode

If you want to explain anything, ask right away in the comment section.

Discussion (0)