CS 102 Laboratory Session Eight

Using Stacks

Goals

Exercise 1 (1 checkoff point)

Download the following files to a directory in your account:

• ex1.cc
• ex2.cc
• Stack.h
• Stack.cc
• Makefile (for Unix users only)

Write a function clear that empties out a Stack. Note that this is not a member function (i.e., it only needs access to the public interface of a stack). Here is its header:

// post: s is an empty stack
void clear (Stack & s);

The source code file ex1.cc contains the header for the function and a program to test it on. When you compile use the command gmake ex1. We've already writen the Makefile for you.

Exercise 2 (2 checkoff points)

The source code file ex2.cc contains a program that determines if a string contains matched parentheses (a printed copy is attached). It will read characters only until it reaches a newline. If the string it read has matched parens it prints "yes", else "no". To compile it use the command gmake ex2.

Compile and run it with strings of unmatched parens and matched parens to see what it does.

1. What does it do on an empty string? i.e., newline by itself.

2. How are sequences of matched parentheses handled? e.g., ()()

3. How does the program handle strings that contain other characters besides parentheses?

4. Here is the algorithm used by the program, which uses a stack: whenever we sees a left parenthesis we push it; whenever we see a right parenthesis if it has a matching left parenthesis, it will be at the top of the stack, and since we found its mate, we pop it now. For a string of matched parenstheses, at the end the stack must be empty.

Show what is on the stack at the point where we have just read (but before we process), i.e., before the switch statement, each of the characters indicated with a carat below it:

()(()()()(()))
  ^
()(()()()(()))
           ^
((((())(
        ^
(()))
    ^ 

You should be able to do this without running the program (i.e., just by examining the program), but if you are unsure, you can use gdb or ddd to trace through and look at the stack object as the actual program is running.

Exercise 3 (2 checkoff points)

Make a copy of ex2.cc called ex3.cc:

cp ex2.cc ex3.cc

Here are some example inputs and the corresponding results for this new program:

((()))          yes
{{{}}}          yes
{{{)))          no
{{}}(){()}      yes
{}}             no
(()             no