Write a c++ program that has the following features, please use 3 space indentation instead of tabs. I will use this as a reference for future coding exercises. Thank you!

Description:

You are going to write a program that checks to see if a string is a palindrome. A palindrome is a word, phrase, number, or another sequence of characters which reads the same backward as forward, such as madam or race car. Sentence-length palindromes may be written when allowances are made for adjustments of capital letters, punctuation, or word dividers, such as A man, a plan, a canal Panama!. (Wikipedia) You will use a stack and a queue to determine if a phrase is a palindrome. You will ignore spaces and punctuation. You may use either a c-string or a c++ string. (Hint: You should store characters on the stack and queue to make this easy.)

The stack class is written for you but will need to be modified to use the correct type. You will need to write the queue class. The Node class will need to be changed to work with the stack and queue classes.

######################################

Stack.cpp code:

#include "node.hpp" class Stack { Node *top; int count; public: Stack(); bool push (float, string); bool pop (); stack_data stack_top (); bool empty(); }; Stack::Stack() { top = NULL; count = 0; } bool Stack::push (float data, string name) { bool success = false; Node *ptr = new Node(data, name); // Check to see if successfully allocated if (ptr != NULL) { // If allocated, check for top if (top != NULL) { // If top isn't NULL, put the pointer into the current Node ptr->set_link (top); } // Set the top equal to the new Node. top = ptr; count ++; success = true; } return success; } bool Stack::pop () { bool success = false; Node *temp; // Check to make sure there are items on the stack if (top != NULL) // if (top) works also { // If there is a top, set success to true success = true; count --; // Save the top pointer so it can be deleted. temp = top; // Set the top pointer to the next data top = top->get_link(); // Delete the former top delete temp; } return success; } stack_data Stack::stack_top() { float data; // Check to make stack isn't empty if (top != NULL) // if (top) works also // Return the data return top->get_data(); // Doesn't handle error case. } bool Stack::empty() { if (top != NULL) return false; else return true; } 

################################

Stack.hpp code:

#ifndef __STACK__ #define __STACK__ #include "node.hpp"

class Stack { Node *top; int count; public: Stack(); bool push (float, string); bool pop (); stack_data stack_top (); bool empty(); }; #endif

################################

Queue.cpp

#ifndef __QueueClassH__ #define __QueueClassH__ #include  // For error-checking purposes //------------------------------------------------- // Main structure of Queue Class: //------------------------------------------------- template  class Queue { public: Queue(int MaxSize=500); Queue(const Queue &OtherQueue); ~Queue(void); void Enqueue(const Elem &Item); // Adds Item to Queue end Elem Dequeue(void); // Returns Item from Queue inline int ElemNum(void); // Returns Number of Elements protected: Elem *Data; // The actual Data array const int MAX_NUM; // The actual spaces will be one more than this int Beginning, // Numbered location of the start and end End; // Instead of calculating the number of elements, using this variable // is much more convenient. int ElemCount; }; //------------------------------------------------- // Implementation of Queue Class: //------------------------------------------------- // Queue Constructor function template  Queue::Queue(int MaxSize) : MAX_NUM( MaxSize ) // Initialize the constant { // This extra space added will allow us to distinguish between // the Beginning and the End locations. Data = new Elem[MAX_NUM + 1]; Beginning = 0; End = 0; ElemCount = 0; } // Queue Copy Constructor function template  Queue::Queue(const Queue &OtherQueue) : MAX_NUM( OtherQueue.MAX_NUM ) // Initialize the constant { Beginning = OtherQueue.Beginning; End = OtherQueue.End; ElemCount = OtherQueue.ElemCount; Data = new Elem[MAX_NUM + 1]; for (int i = 0; i < MAX_NUM; i++) Data[i] = OtherQueue.Data[i]; } // Queue Destructor function template  Queue::~Queue(void) { delete[] Data; } // Enqueue() function template  void Queue::Enqueue(const Elem &Item) { // Error Check: Make sure we aren't exceeding our maximum storage space assert( ElemCount < MAX_NUM ); Data[ End++ ] = Item; ++ElemCount; // Check for wrap-around if (End > MAX_NUM) End -= (MAX_NUM + 1); } // Dequeue() function template  Elem Queue::Dequeue(void) { // Error Check: Make sure we aren't dequeueing from an empty queue assert( ElemCount > 0 ); Elem ReturnValue = Data[ Beginning++ ]; --ElemCount; // Check for wrap-around if (Beginning > MAX_NUM) Beginning -= (MAX_NUM + 1); return ReturnValue; } // ElemNum() function template  inline int Queue::ElemNum(void) { return ElemCount; } #endif /*__QueueClassH__*/ 

################################

The code to check to see if the string is a palindrome should be in the main function. You should have 2 test cases that you test in main one that is palindrome and one that isnt. Then you should ask the user for a phrase until the user wishes to terminate.

Specific information for classes:

Stack class data

top points to the first Node in list

count keeps track of the number of Nodes in list

Stack class functions

Any needed constructors

push adds a Node to the top of the stack

pop Removes a Node from the top of the stack

stack_top Returns the item at the top of the stack without affecting the stack

empty returns true if the stack is empty, false otherwise

Note: Remember that a stack is created in static (automatic memory) and a Node is in dynamic memory.

Queue class data

front points to the first Node in list

rear points to the last Node in list

count keeps track of the number of Nodes in list

Stack class functions

Any needed constructors

enqueue adds a Node to the end of the list

dequeue Removes a Node from the front of the queue

get_front Returns the item at the front of the queue without affecting the queue

empty returns true if the queue is empty, false otherwise

Note: Remember that a queue is created in static (automatic memory) and a Node is in dynamic memory.

There is pseudocode written for the queue class and available under Notes on Blackboard.

Requirements for main:

In the main program, you will test 2 cases; one that is a palindrome and one that isnt. Then you will ask the user for a phrase and indicate whether or not the phrase is a palindrome. You will loop until the user wishes to exit.

Sample Output:

The phrase race car is a palindrome.

The phrase man made is not a palindrome.

Please enter a phrase:

Madam

Madam is a palindrome.