Lab 15: Experiment 1

Working with a stack

The Problem

You've now had several labs to write a variety of programs, often with a variety of code provided to you. For this last lab, you'll write all of the code.

Here's the problem: what happens if we read in a bunch of words, push them all onto a stack, and then, as we pop them off, display them?

The Prediction

So what will happen to the words when they're printed out? Try this out on paper first:

Question #15.1.1: Suppose the words in the sentence "Madam, I'm Adam." were pushed one after the other onto the same stack, and then they were printed as they were popped off. What would be printed?

Now, granted, this is only one example, but perhaps it's enough to make a prediction:

Question #15.1.2: What will the (eventual) program do in general to any sequence of words?

Design

The behavior is quite simple:

The program will create a new empty stack. The program will prompt for and read in a file name from the keyboard, and then it will open that file for input. For each word read in, push it onto the stack. When the end-of-file is reached, the file is closed. Then words are popped off the stack until the stack is empty, and each word that is popped off is printed to the screen.

You can use an output file if you like. We're not really interested in solving this precise problem since it's a little silly. We're really interested in what the stack will do in this situation.

The objects are straightforward:

Description	Type	Kind	Name
the stack of words	stack<string>	varying	theStack
the file name	string	varying	inFileName
the keyboard	istream	varying	cin
the input stream	ifstream	varying	inStream
a word	string	varying	word
the screen	ostream	varying	cout

The operations are fairly straightforward as well. The following list omits the file operations, but you can look them up from previous labs.

Description	Predefined?	Name	Library
create a new stack	yes	stack() constructor	stack
push a word onto the stack	yes	push()	stack
test if stack is empty	yes	empty()	stack
get top value from stack	yes	top()	stack
pop top value from stack	yes	pop()	stack

Declaring a stack is just like declaring a vector or list. Use the exact same syntax, substituting in "stack" appropriately. All of the other operations here will be methods invoked on theStack.

So we end up with this algorithm:

1. Create a new, empty stack theStack.
2. Display a prompt for the program.
3. Read in inFileName.
4. Open inStream (using inFileName), and test that it opened properly.
5. Loop:
   1. Read in word from inStream.
   2. If inStream is at the end-of-file, terminate the loop.
   3. Push word onto theStack.
6. Close inStream.
7. While theStack is not empty:
   1. Display the top of theStack on the screen (followed by some whitespace).
   2. Pop the top value from theStack.

Write the program, compile it, and run it.

The Analysis

Compare your prediction with the actual outcome.

Question #15.1.3: How closely did your prediction match the actual outcome?

A stack is sometimes known as a LIFO container---Last In, First Out. The first item you push onto a stack will be the last one out.

Question #15.1.4: How does LIFO explain the behavior you see from your program?

Terminology