Conditionals, Loops
This check should fail in two possible ways:
If we close a bracket when its matching open bracket is not the most recent
bracket seen, as in (> or }
If we end up with a stray open bracket of any type, as in [() or {
Our solution uses a stack to keep track of the brackets that are open and fails on either of those conditions. Otherwise, it returns True:
def has_balanced_brackets(phrase):
"""Does a given string have balanced pairs of brackets?
Given a string as input, return True or False depending on whether the
string contains balanced (), {}, [], and/or <>.
"""
# START SOLUTION
closers_to_openers = {")": "(", "]": "[", "}": "{", ">": "<"}
# Set of all opener characters; used to match openers quickly.
openers = set(closers_to_openers.values())
# Create an empty list to use as a stack.
openers_seen = []
for char in phrase:
# Push open brackets onto the stack.
if char in openers:
openers_seen.append(char)
# For closers:
#
# - if nothing is open; fail fast
# - if we are the twin of the most recent opener, pop & continue
# - else we're the twin to a different opener; fail fast
elif char in closers_to_openers:
if openers_seen == []:
return False
if openers_seen[-1] == closers_to_openers.get(char):
openers_seen.pop()
else:
return False
# An empty stack means the brackets are balanced.
return openers_seen == []
Notice that the closers_to_openers dictionary uses the closing brackets as keys, rather than the opening brackets. This lets us more easily compare the opening bracket on the top of the stack to any arbitrary closing bracket’s matching opener.