← All lessons

Stack and bracket checking

Sign in · Sign up

Lesson 12.4

A stack is like a pile of plates: you put on top, you take from the top. Last in — first out.

stack = []
stack.append("(")
stack.append("[")
stack.pop()      # "["

The most famous task for a stack is checking that the brackets are placed correctly:

pairs = {")": "(", "]": "[", "}": "{"}

for char in text:
    if char in "([{":
        stack.append(char)
    elif char in ")]}":
        if not stack or stack.pop() != pairs[char]:
            return False
  • an opening bracket is put on the stack;
  • a closing one takes the top one: it must be its pair, otherwise it's an error;
  • the pile is empty but a closing bracket arrives — an error too;
  • at the end the pile must be empty: return not stack.

The check gives the list of strings texts. Write check_brackets(text) and print True or False for each string.

Hint

An opening bracket goes on the stack, a closing one takes the top.

Keep the pairs in a dictionary. There are two errors: the stack is empty while the bracket is a closing one; or the bracket taken off does not match its pair. At the end the stack must stay empty: return not stack.