follow-up - Checking Nested Bracket Levels in Strings Programming Challenge

Question

A follow-up to this question, this post improves on test case issues.

To restate problem parameters, a given string S is considered closed if it:

• Has a matching opening and closing bracket or no brackets at all
• Respects bracket nesting levels
• Has no more than at least one of each bracket type in it

Note that the strings can contain any characters.

Is there a way to this program more efficient?

bracket_levels.py

import re
BRACKETS = dict([
 ('(', ')'),
 ('[', ']'),
 ('{', '}'),
 ('<', '>')
])
def hasClosedBrackets(s: str) -> bool:
 L = len(s)
 if L == 0:
 return False
 if L == 1:
 return not (s in BRACKETS.keys() or s in BRACKETS.values())
 S = s[:]
 def checkSubstring(sub: str):
 for (o, c) in BRACKETS.items():
 if (o in sub and c in sub and sub.index(c) < sub.index(o)) or (sub.count(o) != sub.count(c)):
 return False
 return True
 for (o, c) in BRACKETS.items():
 pattern = r'(?<=\{}).+?(?=\{})'.format(o, c)
 for match in re.findall(pattern, S):
 S.replace(match, '')
 if not checkSubstring(match):
 return False
 return checkSubstring(S)
if __name__ == '__main__':
 tests = list(BRACKETS.keys())
 tests.extend(list(BRACKETS.values()))
 tests += [
 'a',
 '(]',
 '((((',
 '({[<',
 ')}]>({[<',
 '}{',
 '(())',
 '()[{]}',
 'abc',
 '(<[{a}s]>d)f',
 '<as>df',
 '()[{}]',
 '(){}[]'
 ]
 for test in tests:
 print(test, ':', hasClosedBrackets(test))

Output

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

• Stuart: S.replace(match, '') won't do anything without assigning the result back toS.

Answer 1

Here's one opportunity to save cycles. The patterns for the brackets are getting compiled every time hasClosedBrackets is called.

Something like this could be added right after BRACKETS is defined:

brackets_compiled = {
 (o, c): re.compile(r"(?<=\{}).+?(?=\{})".format(o, c)) for o, c in BRACKETS.items()
}

Then the following three lines can be modified:

From:

 for (o, c) in BRACKETS.items():
 pattern = r'(?<=\{}).+?(?=\{})'.format(o, c)
 for match in re.findall(pattern, S):

To:

 for (o, c), pattern in brackets_compiled.items():
 for match in pattern.findall(S):

With this, the patterns are compiled once and that can be looped through each time. This can also be changed to the following if (o, c) aren't needed:

 for pattern in brackets_compiled.values():
 for match in pattern.findall(S):