CMSC 202 Spring 2001

Project 4

Palindromes

Assigned	23 April 2001
Due	6 May 2001

Objectives

This project will allow you to design your own classes, use class templates and use exceptions. You will also continue
to use composition (aggregation) in your class design. You will be using the Stack, Queue and List ADTs discussed
in class. As usual, you will also be creating a makefile for your project.

Description

An interesting phenomenon in the English language is the existence of sentences, words and phrases (SWPs) that read the same forwards and backwards (if you ignore capitalization, punctuation, special characters (dash, apostrophe, etc) and spaces). These sentences, words and phrases are called "palindromes". Perhaps the most famous palindrome is "Madam, I'm Adam". Mr. Frey's favorite palindrome is (you guessed it) "Bob". Any single letter words ("a", "I") are examples of trivial palindromes.

Your project will read SWPs from a text file (one SWP per line, no more than 50 characters) and determine whether or not each SWP is a palindrome. Your program will output each SWP read from the file followed by the phrase "is a palindrome" or "is not a palindrome". If the SWP is not a palindrome, your output will indicate the rightmost and leftmost characters that do not match, proving that it is not a palindrome. See the sample output below.

If this were not a course in object oriented programming using C++, you could write a simple function using loops that determine if a given string is a palindrome or not (if you can't, don't tell anyone). You're not going to have it so easy. You are required to create a class named SWP which contains a line read from the file. The SWP ADT includes a method named isPalindrome( ). That method uses a Stack and a Queue to determine if the the SWP is a palindrome according to the following algorithm

simultaneously push all the characters of the SWP onto a stack and enqueue them onto a queue (ignoring punctuation symbols, special characters and whitespace (spaces, tabs, newlines, etc.).

simultaneously pop a character from the stack and dequeue a character from the queue. If the characters don't match (ignoring upper/lower-case), then the SWP is not a palindrome.

If all the characters are popped/dequeued, and all match (ignoring case) then the SWP is a palindrome.

Your Stack and your Queue must be class templates and must use a List (composition) which is also a class template. You may choose to implement your list as either an array or as a linked list. If you implement it as a linked list, you will also be creating a template for the linked list's Node class. You can start by modifying your linked list code from project 3 (make it a template, add necessary special insert/remove functions), or you may find some code in the text helpful.

Your Tasks:

Write Proj4.C that contains main( ), reads the file, etc.....

Implement the SWP class. Remember that your class definition should be in your .H file and the implementation in your .C file. THIS IS NOT a class template.

Implement the List class as a template (List<T>). You may use either an array implementation or a linked list implementation -- your choice.

Implement the Stack class as a template (Stack<T>). Your stack MUST use a List<T> as its data representation.

Implement the Queue class as a template <Queue<T>). Your queue MUST use a List<T> as its data representation.

Create a makefile that compiles all necessary files (NOT your class templates) and creates an executable named Proj4.

Submit the required files

ADT Definitions

The following ADTs provide the public interface for each class. You may write whatever private methods you feel are necessary. Any function/method prototypes which are given below are intentionally incomplete -- you must decide the complete function signature for any function or class method you write. All data representations in all classes must be private. No public data is allowed. All classes must throw an exception when a run-time error is detected.

The SWP ADT

The SWP class represents a Sentence, Word or Phrase. It supports the following operations.

The "Big-4" -- default constructor, copy constructor, assignment operator (operator=) and destructor.
isPalindrome( ) -- determines if the SWP is a palindrome. If it is not, this method must indicate where (which character position) in the SWP it fails to be a palindrome. Remember that the output must indicate this information if the SWP is not a palindrome.
operator<< -- the overloaded output operator which may be a friend of the SWP class.

Your data representation may assume a maximum SWP size of 50 characters.

The Stack ADT

The Stack ADT was described in class. Your stack must be implemented as a class template. Don't forget to create exception classes to be thrown for any run-time errors the Stack may detect. The Stack supports ONLY the following public operations.

The "Big-4"

push ( ) -- adds a new element to the top of the stack. It is an error to push( ) onto a full stack

pop ( ) -- that removes an element from the top of the stack and returns it to the user. It is an error to pop( ) from an empty stack.

Your Stack's data must be stored in a List.

The Queue ADT

The Queue ADT was described in class. Your queue must be implemented as a class template. Don't forget to create exception classes to be thrown for any run-time errors the Queue may detect. It supports ONLY the following public operations.

The "Big-4"

enqueue ( ) -- adds a new element to the end of the queue. It is an error to enqueue( ) onto a full queue.

dequeue ( ) -- that removes an element from the front of the queue and returns it to the user. It is an error to dequeue( ) from an empty queue.

Your Queue's data must be stored in a List.

The List ADT

The List ADT described in class and used for Project 3 is insufficient for this project. In addition to the operations previously described for project 3, your List class must support the "special" insert and remove functions necessary to support the Stack's push/pop and the Queue's enqueue/dequeue operations. You may also want to declare additional constructor(s). Your List class must be implemented as a class template, but may be either an array or linked list implementation. If you choose a linked list implementation, you will also need a Node class template. If you choose an array implementation, you must you dynamic memory allocation for the array.
Don't forget to create exception classes to be thrown for any run-time errors the List may detect.

The Node ADT

The node is used only by the List class when the list is implemented as a linked list. It is a class template. Because it used only by the List class, it has no public interface. Instead, the List class is declared to be a "friend" of the Node class and directly accesses the private methods and data. The Node class supports only the "Big-4".

The text file

    The text file will contain an unknown number of lines of text. Each line of text will be no more than 50 characters long. Each line in the file is a separate SWP (Sentence, Word or Phrase). Blank lines may appear (by accident) anywhere in the file. Your program should recognize them and ignore them.
    A sample text file can be found in Mr. Frey's public directory
        /afs/umbc.edu/users/d/e/dennis/pub/CMSC202/Proj4/proj4.txt
A plethora of palindromes can be found at http://www.polymorf.org/palindromes.html if you choose to create your own text file for testing.

Requirements and Restrictions

Your main program must be found in Proj4.C Your program must accept a single command line argument which is the name of the file that contains SWPs to test.
For all classes, the definition must be found in the .H file and the implementation found in the .C file. No code is permitted in the header file.
Exception classes must be defined in the .H file of the related object. I.e. any exception objects thrown by the Stack class must be defined in Stack.H and implemented in Stack.C. Exception classes may be minimal.
The only "friend" relationships permitted are

operator << may be a friend of the SWP class
The List class may be a friend of the Node class if you use a linked list implementation

Hints and Reminders

Remember that an object's (or function's) "knowledge" of other objects is limited to it's public interface. Even though the Stack and Queue use the List to store their data, they have no special privileges. The stack and queue methods are limited to using the List's public interface, just like any other function would be.
Don't forget to throw exceptions whenever a run-time error may occur. Also, don't forget your try and catch blocks to handle the errors thrown by the low level objects.
Be sure to test each object separately. This is especially true for testing exception code, since exceptions don't happen when our project is working correctly.
Class templates -- don't forget to #include the .C file at the bottom of the .H file. DO NOT #include the .H file in the .C file or many compiler/linker errors will appear. Use one of the techniques described in class for compiling your .C file to look for syntax errors. This applies to class templates ONLY.
Your class templates DO NOT create .o files; therefore your makefile should not include Stack.o, Queue.o or List.o in any list of necessary object files.

Sample Output

This sample output was created by hand and not generated by any program.
Your output does not have to match exactly, but should print each SWP on a separate line and indicate whether or not the SWP is a palindrome or not. If not, use the ^ character on the next line to indicate the leftmost and rightmost nonmatching characters which prove that the SWP is not a palindrome.

linux3[1]% Proj4 proj4.txt

CMSC 202 Project 4 -- Palindrome testing
File: proj4.txt

    "A Santa at NASA" is a palindrome
    "Able was I, ere I saw Elba." is a palindrome
    "ABCCA" is not a palindrome
      ^ ^
    "Don't nod" is a palindrome
    "evil olive" is a palindrome
    "XYZYX" is a palindrome
    "Won't lovers revolt now?" is a palindrome
    "qwertxytrewq" is not a palindrome
          ^^
linux3[2]%

Makefiles

The "make" utility is used to help control projects with large number of files. It consists of targets, rules, and dependencies.
For this project, simply typing the command make or make Proj4 at the Unix prompt will compile and link your source files with Proj4.C and produce a new executable called Proj4. Typing make clean will remove any extraneous files in your directory such as .o files, and core files. Typing make cleanest removes all .o files, core, Proj4 and backup files made by your editor.
See a documented makefile for more information, or see the Project page for a link to even more info about make

What to Submit

For this project, you must submit the following files. It is your responsibility to submit all files necessary to create your executable so that the graders can simply type "make".

SWP.C and SWP.H -- the sentence/word/phrase implementation and header files Note that this is NOT a template class.
Your makefile -- it must be named "makefile" or "Makefile". The graders will simply type "make" and your files must compile and link all source files as appropriate
Proj4.C -- your main project driver
Stack.C and Stack.H -- the stack class template and Stack related exception classes
Queue.C and Queue.H -- the queue class template and Queue related exception classes
List.C and List.H -- the List class template and List related exception classes
Node.C and Node.H -- the Node class template and Node related exception classes (required only if the List is implemented as a linked list)
If you create your own exception header files and source code files, be sure to submit them as well.