AI Hints
Home›DSA in Python Tutorial›Stacks and Queues
DSA in Python · Lesson 32 of 132

Practice: Balanced Brackets

Every opener has a closer.

⏱ 2 min read▶ Video at 37:14🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Code editors check that every bracket is closed, in the right order. Round brackets, square brackets, and curly braces. Pause. Why would a stack be perfect for this?

Practice: Balanced Brackets
From the video: Practice: Balanced Brackets
  • Every bracket closed
  • In the right order
  • Why a stack?

Matching with a stack

Each opening bracket is pushed onto the stack. When a closing bracket arrives, the top of the stack must be its partner. If it isn't, or the stack is empty, the brackets are broken. At the end, the stack must be empty, or something was never closed. Run it. The first two are balanced. The last two are not.

brackets.pypython
def balanced(text):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for t in ["(a[b]{c})", "{[()()]}", "([)]", "(("]:
    print(t, balanced(t))
Output
(a[b]{c}) True
{[()()]} True
([)] False
(( False

Stacks are everywhere

Whenever the most recent thing must be dealt with first, think stack. Matching brackets, undo history, and evaluating maths expressions. Even Python itself uses a stack to keep track of which function is running, and where to return to. We'll see that soon, in recursion.

keyvalue
Bracketsmatch the latest opener
Undoreverse the latest change
Calculatorsevaluate expressions
Function callsthe call stack

Summary

Push the openers, and pop to check each closer. An empty stack at the end means balanced. Next, queues. First in, first out.

Key takeaways
  • Push openers
  • Pop on closers
  • Empty at the end
Next up: Queues — first in, first out