Goal: Stacks and Queues to implement a programming solution Make sure you thoroughly read and understand the directions before you begin. Problem Statement A palindrome is a character string that is equal to its reverse. A simple palindrome would be a word that is the same spelled forward or backward such as level. A palindrome can also be a phrase such as "Never odd or even". This is not a simple palindrome, since making it the same as its reverse requires that we ignore spaces and punctuation marks. For this assignment, a palindrome is defined to be a character string, where all non-alphabetic characters are ignored, and upper-case and lower-case versions of the same letter are viewed as equivalent. Alphabetic characters includes characters A through Z and a through z inclusive. Thus punctuation marks, digits, space, tab, carriage return, hyphens, underscores, and other nonalphabetic characters are ignored in the palindrome decision process. The assignment is to write a program that does the following. You will need to define extra functions to complete some of these tasks such as the first two bullet items: ? Prompts the user to type in a character string ? Gets the characters and stores them in a stack data structure. ? Makes use of the stack and a queue data structure to check for a palindrome. ? Defines a function isPalindrome that determines whether the string is a palindrome. The function isPalindrome returns 1 if x is a palindrome, and 0 if x is not a palindrome. int isPalindrome(char *x) ? Displays an appropriate message on the screen that indicates the string and whether the string is a palindrome or not. Programming Hints ? Your program will involve three files: main.c, Palindrome.c, and Palindrome.h. o The file Palindrome.h contains exactly one line, the prototype of your function isPalindrome. o The file Palindrome.c contains the definition of your function isPalindrome. It should have your name, the date, and #include "Palindrome.h". It should not contain a main function. o Your file main.c contains your main function. That file should also specify any #include files, including Palindrome.h. Your main program should thoroughly test the Palindrome program ? The following header files must be defined and included in the source code using the stacks and queues. o #include stack.h o #include queue.h You will need to submit these 2 files with your submission of the other 3 files mentioned above. ? The following functions may be helpful and are provided by the C Standard Library: o int isalpha(char c) // returns non-zero integer if c is an alphabetic character, 0 if not o char toupper(char c) // returns the upper-case version of an alphabetic character Testing Suggestions A list of examples is given below in a C++ variable declaration. Make sure that you test for the following situations. 1. Test that your program returns a value of 1 on the examples. 2. Test that your program returns 0 if you change one of the characters in any of the examples. Examples "A dog, a panic in a pagoda" "A dog, a plan, a canal, pagoda" "A man, a plan, a canal-- Panama! // punctuation and spaces are ignored "civic" "If I had a hi-fi" "Do geese see God?" "Madam, Im Adam." "Madam, in Eden, Im Adam." "Neil, a trap! Sid is part alien!" "Never odd or even" "No devil lived on." "No lemons, no melon" "racecar" "RACEcar" // uppercase equals lowercase Rats live on no evil star." "Red rum, sir, is murder!" "Rise to vote, sir." "rotator" "rotor" "Step on no pets." "Was it a cat I saw?" "Was it a car or a cat I saw?" "Yawn a more Roman way. " Extra Credit (20 Points) ? Allow the user to choose whether to enter a string to check or a file to check ? In the case of a file, read each line of text from an input data file ? Write to the screen all lines that are palindromes with an appropriate message

//Stack.h

#ifndef STACK_H #define STACK_H #include using namespace std;

// Stack template template class Stack { private: T *stackArray; int stackSize; int top;

public: //Constructor Stack(int); // Copy constructor Stack(const Stack&); // Destructor ~Stack(); // Stack operations void push(T); void pop(T &); bool isFull(); bool isEmpty(); }; //*************************************************** // Constructor * //***************************************************

template Stack::Stack(int size) { stackArray = new T[size]; stackSize = size; top = -1; }

//*************************************************** // Copy constructor * //***************************************************

template Stack::Stack(const Stack &obj) { // Create the stack array. if (obj.stackSize > 0) stackArray = new T[obj.stackSize]; else stackArray = NULL; // Copy the stackSize attribute. stackSize = obj.stackSize; // Copy the stack contents. for (int count = 0; count < stackSize; count++) stackArray[count] = obj.stackArray[count]; // Set the top of the stack. top = obj.top; }

//*************************************************** // Destructor * //***************************************************

template Stack::~Stack() { if (stackSize > 0) delete [] stackArray; }

//************************************************************* // Member function push pushes the argument onto * // the stack. * //*************************************************************

template void Stack::push(T item) { if (isFull()) { cout << "The stack is full. "; } else { top++; stackArray[top] = item; } } //************************************************************* // Member function pop pops the value at the top * // of the stack off, and copies it into the variable * // passed as an argument. * //*************************************************************

template void Stack::pop(T &item) { if (isEmpty()) { cout << "The stack is empty. "; } else { item = stackArray[top]; top--; } }

//************************************************************* // Member function isFull returns true if the stack * // is full, or false otherwise. * //*************************************************************

template bool Stack::isFull() { bool status; if (top == stackSize - 1) status = true; else status = false; return status; }

//************************************************************* // Member function isEmpty returns true if the stack * // is empty, or false otherwise. * //*************************************************************

template bool Stack::isEmpty() { bool status; if (top == -1) status = true; else status = false; return status; } #endif

//Queue.h

#ifndef QUEUE_H #define QUEUE_H #include using namespace std;

// Stack template template class Queue { private: T *queueArray; // Points to the queue array int queueSize; // The queue size int front; // Subscript of the queue front int rear; // Subscript of the queue rear int numItems; // Number of items in the queue public: // Constructor Queue(int); // Copy constructor Queue(const Queue &); // Destructor ~Queue();

// Queue operations void enqueue(T); void dequeue(T &); bool isEmpty() const; bool isFull() const; void clear(); };

//*************************************************************** // This constructor creates an empty queue of a specified size. * //*************************************************************** template Queue::Queue(int s) { queueArray = new T[s]; queueSize = s; front = -1; rear = -1; numItems = 0; }

//*************************************************************** // Copy constructor * //*************************************************************** template Queue::Queue(const Queue &obj) { // Allocate the queue array. queueArray = new T[obj.queueSize]; // Copy the other object's attributes. queueSize = obj.queueSize; front = obj.front; rear = obj.rear; numItems = obj.numItems; // Copy the other object's queue array. for (int count = 0; count < obj.queueSize; count++) queueArray[count] = obj.queueArray[count]; }

//*************************************************************** // Destructor * //*************************************************************** template Queue::~Queue() { delete [] queueArray; }

//*************************************************************** // Function enqueue inserts a value at the rear of the queue. * //*************************************************************** template void Queue::enqueue(T item) { if (isFull()) cout << "The queue is full. "; else { // Calculate the new rear position rear = (rear + 1) % queueSize; // Insert new item queueArray[rear] = item; // Update item count numItems++; } }

//*************************************************************** // Function dequeue removes the value at the front of the queue * // and copies t into num. * //*************************************************************** template void Queue::dequeue(T &item) { if (isEmpty()) cout << "The queue is empty. "; else { // Move front front = (front + 1) % queueSize; // Retrieve the front item item = queueArray[front]; // Update item count numItems--; } }

//*************************************************************** // isEmpty returns true if the queue is empty, otherwise false. * //*************************************************************** template bool Queue::isEmpty() const { bool status;

if (numItems) status = false; else status = true;

return status; }

//*************************************************************** // isFull returns true if the queue is full, otherwise false. * //*************************************************************** template bool Queue::isFull() const { bool status;

if (numItems < queueSize) status = false; else status = true;

return status; }

//***************************************************************** // clear sets the front and rear indices, and sets numItems to 0. * //***************************************************************** template void Queue::clear() { front = queueSize - 1; rear = queueSize - 1; numItems = 0; } #endif