CP164 Study Guide - Final Guide: Backtracking
Notes - The Stack ADT
The following is an example of a fairly simple maze. However, it doesn't matter how complex
the maze is, so long as we can identify locations in the maze where choices can be made we can
successfully search the maze using a stack and the concept of backtracking.
A Sample Maze
In this sample maze, the circles represent a decision point, and the letters represent one of the
paths that can be taken at the decision point. The rules to follow when solving the maze are:
Move to an intersection and add all the choices at that intersection onto the stack. Add them to
the stack in alphabetical order.
When you then need to make a decision as to where to go next, pop an element from the stack
and go in that direction.
The result stack for this maze follows:
A Sample Stack-Based Solution
A stack-based solution to this kind of problem is called a Depth-First Search. Such a search
takes you to the end of the maze (assuming you don't find the exit right away) before
backtracking to visit intersections bypassed earlier. (Later, when working with queues, we will
examine a Breadth-First Search.)
Stacks - Balanced Brackets
Stacks can be used to check if brackets (parentheses, square, brace) are properly balanced
in algebraic methods. E.g. Are the following methods correctly written?
{a × 2 - [(c - d) × 4]} × sin(x - y)
{a × 2 - [(c - d) × 4}]
This program can be solved with the algorithm:
Initialize a stack.
Traverse the expression one character at a time
If we see a left bracket of any kind, push it onto the stack.
If we see a right bracket of any kind, pop the top of the stack and see if it is the left
complementary to the right bracket.
The expression is invalid if one of the following is true:
An item popped from the stack does not match the corresponding right bracket.
We encounter a right bracket, but the stack is empty.
We reach the end of the expression but the stack is not empty.
Document Summary
The following is an example of a fairly simple maze. However, it doesn"t matter how complex the maze is, so long as we can identify locations in the maze where choices can be made we can successfully search the maze using a stack and the concept of backtracking. In this sample maze, the circles represent a decision point, and the letters represent one of the paths that can be taken at the decision point. The rules to follow when solving the maze are: Move to an intersection and add all the choices at that intersection onto the stack. Add them to the stack in alphabetical order. When you then need to make a decision as to where to go next, pop an element from the stack and go in that direction. A stack-based solution to this kind of problem is called a depth-first search.
