Calvin University CS 112 Project 8

CS 112 Project 8: Queues (and Stacks)

Objectives:

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

Introduction

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

Convert your ArrayQueue into a template.
Add a new method to your ArrayQueue class:
- aQueue.setCapacity(newCapacity), that changes the capacity of aQueue to newCapacity. (This is much trickier than Stack::setCapacity(): if newCapacity is zero OR newCapacity or < getSize(), setCapacity() should throw an exception; otherwise, it should allocate a new array with the new capacity, copy the values from the old array into the new array, and deallocate the old array.) To help you see all the things that can go wrong, you should make certain your method passes all the tests in this test method before working on the rest of the project.
Use your Stack<Item> and ArrayQueue<Item> to solve a problem.

As usual, you should use test-driven development to accomplish these tasks.

The Problem

You are to design and build a palindrome detector class. For our purposes, a palindrome is a line of text in which the alphabet characters are the same when read forwards and backwards. For example, the lines:

   Madam, I'm Adam.
   A man, a plan, a canal, Panama!

are both palindromes.

Your palindrome detector is to read an input file and create an output file that is an exact copy of the input file, except that 3 asterisks (***) are printed at the end of each line that is a palindrome. Thus, if the input file contained the two lines above, the output file should contain:

   Madam, I'm Adam. ***
   A man, a plan, a canal, Panama! ***

Your class constructor should accept and save the names of the input and output files.

To accomplish this, your class should provide a detectPalindromes() method that opens streams to the input and output files, processes the input file line-by-line, and produces the corresponding output file. (Hint: use getline() to read a line into a string, immediately write that string to the output file, then process the string character-by-character.) Don't forget to close the streams at the end of this method.

To "process" a given string str, your checker should call an isPalindrome(str) method that returns true or false based on whether or not str is a palindrome. This method should process the string character-by character, as follows:

For each character in the string: If that character is a letter, your program should:
1. convert it to lower case;
2. push it onto a stack; and
3. append it to a queue.
When the string's characters have been loaded into the stack and queue, repeat these steps until the stack and queue are empty:
1. Pop a char from the stack into ch1;
2. Remove a char from the queue into ch2;
3. If ch1 and ch2 are different, then return false (the line is not a palindrome);
Return true.

This algorithm works because a stack is a LIFO structure while a queue is a FIFO structure. When we have added the characters from a line to each structure, popping the stack gives us the line's last character on the line, while removing from a queue gives us the line's first character. As soon as we find a mismatch in these characters, we know the line is not a palindrome; However, if we reach the bottom of the stack and the end of the queue without finding any mismatch, then we have a palindrome.

The twist is that for each line to be processed, your method should define your stack and queue with initial capacities of 1. You are to "wrap" the push() and append() calls in try-catch blocks. If either throws an exception (because the structure is full), your exception-handler code should:

Use setCapacity() and getCapacity() to double the structure's capacity; and
Invoke push() and append() again to push/append the character onto the (now larger) structure.

There is one special case to cover: a blank line can (trivially) be considered to be a palindrome, but we will not do so -- your class should not mark blank lines as palindromes.

You may find some of the functions in the <cctype> library to be useful for this project.

As always, if you get to the point where you cannot figure out what is wrong, use the debugger, as it will let you trace the execution of your code one step at a time!

You should use test-driven development to build your class. Write a test class and strong test-methods for the methods in your palindrome detector class. When your palindrome detector passes all of your tests, try it on this input file as a final test. Our grader will be using it to test your program.

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 using this input file. 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 proj08 folder, copied to your /home/cs/112/current/yourUserName/ folder.

CS > 112 > Projects > 08

This page maintained by Joel Adams.