Calvin College 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:

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 < 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.
Convert your Queue into a template; and
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.

If you get to the point where you cannot figure out what is wrong, use the debugger!

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.

Submit

A hard copy of this grade sheet, attached to a hard copy of a script file that lists the files in your project, shows that it compiles/links correctly, and shows it correctly running and providing the required functionality.
An electronic copy of your project, in your /home/cs/112/current/yourUserName/proj8 folder.

CS > 112 > Projects > 08

This page maintained by Joel Adams.