CS210 Lab: Stacks and Exception Handling


Prelab Questions:

For a review of relevant topics click here.

Highlights of This Lab:

Lab Exercise:


Click the little computer above for a detailed description.
For this excercise you will be asked to implement a stack to recognize whether or not a set of parentheses is well-formed.

1. Definition of a Stack

A Stack is "an abstract data type in which elements are added and removed from only one end; a 'last in, first out' (LIFO) structure."
(C++ Plus Data Structures, page 196)

In a Stack implementation, items are added to and removed from the top of the pile. Consider the pile of papers on your desk. Suppose you add papers only to the top of the pile or remove them only from the top of the pile. At any point, the only paper that is visible is the one on top. What you have is a Stack.

1.1 Applications of a Stack

Here are a few examples of where stacks would be used:

1.2 Typical Operations of a Stack

     
  • bool IsEmpty
  •   Determines whether the stack is empty
         
  • bool IsFull
  •   Determines whether the stack is full
         
  • Push(ItemType item)
  •   Adds an item to the top of the stack
         
  • Pop()
  •   Removes top item from the stack
         
  • ItemType Top()
  •   Returns a copy of the top item on the stack

    2. Application: Determining Well-Formed Expressions with Parenthesis

    The following section outlines an algorithm for determining whether or not an expression is well formed. Later, in the lab exercise, you will be given a chance to play with and modify this program.

    A classic use of a stack is for determining whether a set of parenthesis is "well formed". What exactly do we mean by well formed? In the case of parenthesis pairs, for an expression to be well formed, a closing parenthesis symbol must match the last unmatched opening parenthesis symbol and all parenthesis symbols must be matched when the input is finished.

    Consider the following table demonstrating Well-Formed Versus Ill-Formed Expressions:
    Well-Formed Expressions Ill-Formed Expressions
    ( x x x [ ] ) ( x x x [ )
    ( ) [ ] { } ( (
    { ( x x x x x ) ( ) } { x x x x x ) ( ) }

    Why do we care about balancing parenthesis?
    Because the compiler looks for balanced parenthesis in such situations as:

    2.1 The Algorithm

    Given an expression with characters and parenthesis, ( ), [ ], and { }, determine if an expression is well-formed by using the following algorithm in conjunction with a stack.
    Read in the expression character by character. As each character is read in:

    The expression:

    (x{x[]}x)

    yields the following computation

    '(' : Push (
    'x' : Ignore
    '{' : Push {
    'x' : Ignore
    '[' : Push [
    ']'

     
    : Get top of stack, openSymbol='['
       Pop
       Compare if '[' matches ']'
    '}'

     
    : Get top of stack, openSymbol='{'
       Pop
       Compare if '{' matches '}'
    'x' : Ignore
    ')'

     
    : Get top of stack, openSymbol='('
       Pop
       Compare if '(' matches ')'
    '\n' : Print expression is well-formed

    Or graphically:


    3. Lab Exercise

    Stacks and Exception Handling

    Test Plan for the Balanced Parenthesis Evaluation Program
    # Parenthesis Expression Expected Result Checked
    1   (x)    
    2   (x{})    
    3   (x{x[]})    
    4   (x[x)]    
    5   (x(x[]x    
    6   (xx)]    
    7   (x(((((    


    4. Postlab Exercises

    For postlab exercices, click here.

    CS Dept Home Page
    CS Dept Class Files
    CS210 Class Files


    Copyright: Department of Computer Science, University of Regina.