CS3304 Data and Information Structures

Project 2. A Palindrome-Checker Program Using Stack and queue

Purpose: This project is designed to exercise the creation and use of stack and queue. Stacks and queues are studied in Chapter 7 (Stacks) and Chapter 8 (Queues).

Software to use: Use Visual C++ or Visual Studio.Net to develop and test your program.

Problem description: A palindrome is a string that reads the same forward and backward. We will create a text file containing strings one per line. Your program needs to read from the file and determine whether each line is a palindrome. You are required to use a stack and a queue to determine whether a string is a palindrome.

Input: The input should be read from a text file that contains a list of strings, one per line. No assumptions are made on the number of lines the file has. Your program should continue to read until all lines have been processed. For example, the input file may look like:

adda

This is a palindrome

Is this siht sI

Resound dnuoseR!

...

Output: The program should echo-print to the screen the strings read from the file, followed by an assertion either the string is a palindrome or the string is not a palindrome. For example, the output corresponding to the above input can be:

adda    This is a palindrome

This is a palindrome    This is not a palindrome

Is this siht sI    This is a palindrome

Resound dnuoseR!    This is not a palindrome

...

Requirements on the programming: Use a stack and a queue to do the comparisons. When a string is read, push each character onto a stack and simultaneously add it to a queue. When the entire string is read, the program should use the basic stack and queue operations to determine if the string is a palindrome. You should do a pair-wise comparison on characters from the stack and the queue. If all pairs are the same, the string is a palindrome; otherwise, not. To receive full credit, you must use stack and queue to design the program. You can choose any implementation of the stack or the queue to design the Stack and the Queue class. Make sure you include necessary operations in the classes so that the comparisons can be done.

Turn-in: A print-out of your program and a disk containing the source code in C++ and the test input file(s).