DSA Factory
Free lessonsStacks and queues · Stage 0 · Last in, first out · Step 3

Brackets that match

The newest open bracket must close first. About 10 minutes.

The newest open bracket closes first

In the text {[()]}, the round bracket opened last, so it must close first. Then the square one closes, then the curly one. Like nesting boxes inside each other, the last one opened is the first one closed: last in, first out.

So keep the open brackets on a stack.

An opening bracket: push it.
A closing bracket: the top must be its partner. Pop it.
How many brackets are open after each character of "([])"
1
0
2
1
1
2
0
3
i

( opens. Push it. Stack: (

Move 1 of 4

Three ways to fail

A closer arrives and the stack is empty: there is nothing for it to close. A closer arrives and the top is a different kind, as in a round bracket closed by a square one. Or the text ends with open brackets still waiting on the stack.

To look at the top without taking it, use the last item of the list in Python, top in C++, peek in Java, or the last index in JavaScript.

Closer on an empty stack: answer no.
Leftovers at the end: some bracket never closed: answer no.
In code
partner = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
    if ch in "([{":
        stack.append(ch)
    elif not stack:
        return False
    elif stack.pop() != partner[ch]:
        return False
return not stack
Quick check

Reading from the left, at which character do you first know the string is unbalanced?

s = "[(]"
  1. AThe ] at index 2
  2. BThe ( at index 1
  3. CIt's balanced
Show the answer

The ] at index 2. The top of the stack is (, but ] needs a [. That's a mismatch.

Your problem

Balanced brackets

s has only the brackets ( ) [ ] { }. It's balanced when every opening bracket is closed by one of the same kind, and the most recently opened bracket is always the next to close. Return true if s is balanced. An empty string is balanced.

Example
s = "{[()]}()" → true

0 ≤ length of s ≤ 100,000 · s has only ( ) [ ] { }

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding