Do the brackets match?
Every ( needs a ), every [ a ] and every { a }, closed in the right order. Watch a program check an expression with a stack: push each opening bracket, pop it when the matching one closes, and stop at the first bracket that does not fit.
Core concept
To check brackets, push each opening bracket on a stack; a closing bracket must match the bracket on top, which is popped; at the end the stack must be empty
Topic: Data structures
In maths and in programs, brackets come in pairs: ( with ), [ with ] and { with }. They can sit inside one another, like {[( )]}, but the last one opened must be the first one closed. A stack is exactly the right tool, because the last item in is the first item out. The program reads the expression one character at a time. An opening bracket is pushed on the stack. A closing bracket must match the bracket on top of the stack: if it does, that bracket is popped; if it does not, or the stack is empty, the brackets do not match and the program can stop at once. When the expression ends, the stack must be empty, or some bracket was never closed. Code editors use this check to warn you when you forget a bracket.
What you will learn
- Explain why the last bracket opened must be the first one closed.
- Trace a stack of brackets as an expression is read.
- Find the first bracket where an expression goes wrong.
- Name the three ways the brackets can fail to match.
Before you start
- Know how push and pop work on a stack.
Materials
- A notebook to draw the stack
Equipment
- None
Procedure
- Check the expression (A+[B]) and watch the stack.
- Check (A+[B)] and find where it goes wrong.
- Check ((A+B) and see what is left on the stack.
- Answer the practice challenges.