Programming Challenge - Capturing Bracket Levels

Question

I don't have a formal description for this problem, but here are the parameters:

• Given a string S check that each opening bracket has a matching closing bracket.
• Any nesting violations are invalid.
• Assume multiple nested sets of similar brackets are invalid.

Because the nesting level matters and we can't just arbitrarily count brackets, my solution is to generate an array of substrings that contain each bracket level and check for violations.

Is there a way to make this more efficient?

bracket_levels.py

import re

def hasClosedBrackets(s: str) -> bool:
    brackets = dict([('(', ')'), ('[', ']'), ('{', '}'), ('<', '>')])

    for (opener, closer) in brackets.items():
        pattern = r'(?<=\{}).+?(?=\{})'.format(opener, closer)

        for match in re.findall(pattern, s):
            for (o,c) in brackets.items():
                if match.count(o) != match.count(c):
                    return False

    return True


# The first four test cases are true, the last four are false
for test in ['(){}[]', '()[{}]', '<as>df', '(<[{a}s]>d)f', '()[{]}', '<as(>df)', '{as<df}', '(())',]:
    print(test, ':', hasClosedBrackets(test))

Output

(){}[] : True
()[{}] : True
<as>df : True
(<[{a}s]>d)f : True
()[{]} : False
<as(>df) : False
{as<df} : False
(()) : False

Answer 1

Unfortunately, your current strategy is doomed by its optimism. Why? Because the regular expression is premised on checking only those portions of the string containing matching brackets. Parts of the string not enclosed by matching brackets are ignored. And if those parts contain any bracket characters, they will slip through the cracks. For example, all of these invalid strings return true:

(
{
[
<
)
}
]
>
(]
((((
({[<
)}]>({[<

The internet has lots of discussion of a classic, and quite elegant, algorithm for this problem, using a stack (a Python list will do the trick). Ditch the regex; append and pop will do everything you need.

Answer 2

I don’t believe you’ve got enough test cases. For example, hasClosedBrackets("}{") returns True, but I don’t think it should.

You need to rethink your algorithm — unless True is actually expected for that case, in which case you need to improve your formal description.

---

In terms of efficiency, your brackets is defined as a dictionary, but you are never using it as one. A simple list of pairs would suffice, and is actually shorter to code:

brackets = ('(', ')'), ('[', ']'), ('{', '}'), ('<', '>')

… and use just brackets everywhere you are using brackets.items()

Since a string can be treated as a list of characters, you could even go really compact and use:

brackets = '()', '[]', '{}', '<>'

… which is visually much less cluttered, but may be considered too surprising.