Calvin University CS 112 Project 7

CS 112 Project 7: Stacks and Exceptions

Objectives:

Practice building Stack operations.
Use a Stack to solve a problem
Practice using exceptions.

Introduction

This week's project is a single person project. The project is to:

Add some new methods to your Stack class:
- aStack.getSize(), that returns the number of items currently in aStack;
- aStack.getCapacity(), that returns the current capacity of aStack; and
- aStack.setCapacity(newCapacity), that changes the capacity of aStack to newCapacity. Note that if the new capacity is different from the old capacity, changing the capacity involves dynamically allocating a new array that is the new size, copying the Items from the old array into the new array, and deallocating the old array. (This one is slightly tricky: if newCapacity is zero OR newCapacity < getSize(), your setCapacity() method should throw an exception, to ensure that items are never lost.)
Convert your Stack into a Stack<Item> template; and
Use your Stack<Item> to solve a problem.

You are not to add any new instance variables to your Stack class. As usual, you should use test-driven development to create the new operations. You may write and use a single test-method to test all three operations. Make certain you thoroughly test your setCapacity() method, as this method is very easy to write incorrectly.

The Problem

Professor Y.R. Teop from the English Department specializes in the study of Reverse Poems, which are poems that can be read either backwards or forwards, usually with significant changes to their meanings. For example, here is a poem titled Love?, whose author is unknown:

   Love?
   Anonymous

   I don't love you anymore...
   I would be lying if I said
   That I still love you the way I always did.
   I'm sure
   Nothing was in vain.
   And I feel inside of me that
   You mean nothing to me
   I could never really say that
   Our time together matters.
   I feel more and more that
   I'm forgetting you...
   And I will never use the phrase
   I love you.
   I'm sorry but I must tell the truth.

Reading the poem top-to-bottom produces one meaning, but reading the poem bottom-to-top produces a quite different meaning. However, actually reading the poem from bottom to top is clumsy and inconvenient.

Prof. Teop wants us to write a program that will make it easier to compare the forward and backward versions of a poem. Here is a program to do so:

   /* main.cpp
    * ...
    */

   #include "ReversePoem.h"
   #include <iostream>
   using namespace std;

   int main() {
      cout << "\nEnter the name of the poem file: ";
      string poemFile;
      cin >> poemFile;

      ReversePoem reversePoem(poemFile);
      cout << reversePoem.getTitle() << "\n"
           << reversePoem.getAuthor() << "\n"
           << "\n*** Top-To-Bottom ***\n\n"
           << reversePoem.getBody() 
           << "\n*** Bottom-To-Top ***\n\n"
           << reversePoem.getBodyReversed()
           << endl;
   }

To illustrate its execution, a sample run of the program might behave as follows:

   Enter the name of the poem file: poems/love.txt

   Love?
   Anonymous

   *** Top-To-Bottom ***

   I don't love you anymore...
   I would be lying if I said
   That I still love you the way I always did.
   I'm sure
   Nothing was in vain.
   And I feel inside of me that
   You mean nothing to me
   I could never really say that
   Our time together matters.
   I feel more and more that
   I'm forgetting you...
   And I will never use the phrase
   I love you.
   I'm sorry but I must tell the truth.

   *** Bottom-To-Top ***

   I'm sorry but I must tell the truth.
   I love you.
   And I will never use the phrase
   I'm forgetting you...
   I feel more and more that
   Our time together matters.
   I could never really say that
   You mean nothing to me
   And I feel inside of me that
   Nothing was in vain.
   I'm sure
   That I still love you the way I always did.
   I would be lying if I said
   I don't love you anymore...

The problem is that the ReversePoem class does not exist. Your task is to complete the program for Prof. Teop by building the ReversePoem class that the preceding program uses. In terms of methods, you will need to define:

The ReversePoem() constructor, which takes as an argument the name of the file containing a reverse poem.
The getTitle() method, which returns the poem's title.
The getAuthor() method, which returns the poem's author.
The getBody() method, which returns a string consisting of the poem's body in its original form.
The getBodyReversed() method, which returns a string consisting of the poem's body in its reversed form.

These five methods should be sufficient to solve the problem. Each method must perform its operation in constant (O(1)) time, except for the constructor which may take linear (O(N)) time, where N is the number of lines in the poem.. (Hint: Each method except the contructor is a "getter".)

As with your Stack methods, you are to use test-driven development to create these methods and build an automated unit test to test each method. For that purpose, here is a very simple reverse poem:

   Cats 
   Leo J. Smada

   I love it when cats rub against me.
   I could never say
   I hate those furry felines.

You may assume that each reverse poem begins with its title on one line, its author on the next line, then a blank line, and finally the body of the poem.

To achieve the desired performance, your ReversePoem() constructor should use your Stack template to solve this problem. To do so, your constructor will need to read the body of the poem from the input file one line at a time, push those lines onto your stack (which should be a local variable), and pop them from the stack in reverse order.

The twist is that in order for your ReversePoem constructor to handle poems of arbitrary sizes, you are to define your stack with an initial capacity of 1 and "wrap" your push() calls in a try-catch block. If push() throws an exception (i.e., because the stack is full), your exception-handler code should:

Use setCapacity() and getCapacity() to double your stack's capacity; and
Invoke push() again to push the string onto the (now larger) stack.

To help with your final testing, here are several reverse poems that you can use to try out your project. You can avoid cluttering your project by making a folder within your project named poems, and storing all of these poems within that folder.

If you get to the point where you cannot figure out what is wrong, practice and develop your skills using the debugger!

Preparing to Submit

Create a script file in which you use ls to list all your project's files, use cat to display the contents of each file, and build+run your project to demonstrate that it works correctly. Make certain that your script file is located in your project folder.

Our grader will grade your submission based on the categories given in this grade sheet, so you should make certain all of those categories are covered.

Submit

An electronic copy of your proj07 folder, copied to your /home/cs/112/current/yourUserName/ folder.

CS > 112 > Projects > 07

This page maintained by Joel Adams.