3
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I'm aware of the bracket counting problem and its solutions using a stack, however such a solution did not pass all of my tests. This is why I created this approach. You're right on those other test cases though, and I've fixed those. \$\endgroup\$
    – T145
    Mar 20, 2022 at 15:47
  • 1
    \$\begingroup\$ @T145 Are you suggesting that a widely known/taught algorithm has flaws? That would be big news, if true! I hope you're only saying that you tried to implement it, and the attempt contained a mistake. \$\endgroup\$
    – FMc
    Mar 20, 2022 at 16:28
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.