Introduction to Stack Pattern

You are given a string that contains brackets. Your task is to check whether the brackets are balanced.

A string is balanced when:

• every opening bracket has a matching closing bracket, and
• the brackets close in the correct order.

{[()]}   balanced
{[(])}   not balanced

You could scan the string many times. On each scan, remove pairs such as (), [], and {}. If the string becomes empty, it is balanced.

This method works, but it can take O(N²) time. In the worst case, one scan removes only one pair.

There is a better way