Assignment: Palindrome Checker Using Stack and Queues

[mysiarobin1987]

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.

I have come up with the following code, but when I enter a string I get the error "Program5.exe has stopped working". Please help :-)

//main.cpp

#include<iostream>

#include<cstdio>

#include <string>

#include "palindrome.h"

#include "Queue.h"

#include "Stack.h"

using namespace std;

int main(){

char *x;

cout << "Enter a char string"<<"\n";

gets(x);

if(isPalindrome(x)==0)
{

cout<<"The string is not palindrome\n";

}

else

cout << "The string is palindrome\n";

return 0;

}


//palindrome.cpp
#include<iostream>

#include "isPalindrome.h"

#include "stack.h"

#include "queue.h"

using namespace std;

int isPalindrome(char *x){

int init_size = 100;

Stack<int> s(100);

Queue<int> q(100);

int i=0;

while(*(x+i)!='\0'){

char c = *(x+i);

int k = 0;

bool flag = false;

if(c-'a'>=0 && c-'a'<=25){

k=c-'a';

flag = true;

}

if(c-'A' >=0 && c-'A'<=25){

k=c-'A';

flag=true;

}

if(flag){

s.push(k);

q.enqueue(k);

}

i+=1;

}

/*cmp of string and reverse string*/

int ans = 1;

while(!s.isEmpty() && !q.isEmpty()){

int tp,fr;

s.pop(tp);

q.dequeue(fr);

if(tp!=fr){

ans = 0;

return ans;

}

}

return ans;

}

[zaphraud]

Hi! Was this made in a development environment? I'm trying to follow the #include statements to files but you've only posted the .cpp's without the .h files - which would be crucial to understanding what's going on. Splitting the posted code into the two named files doesn't help resolve the problem.

Can you post your .h files as well, if there are any in the directory that you got the code you wrote from?

[mysiarobin1987]

Sorry zaphraud....here you go! Thanks for the reply.

//Queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
using namespace std;

// Stack template
template <class T>
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 <class T>
Queue<T>::Queue(int s)
{
   queueArray = new T[s];
   queueSize = s;
   front = -1;
   rear = -1;
   numItems = 0;
}

//***************************************************************
// Copy constructor                                             *
//***************************************************************
template <class T>
Queue<T>::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 <class T>
Queue<T>::~Queue()
{
   delete [] queueArray;
}

//***************************************************************
// Function enqueue inserts a value at the rear of the queue.   *
//***************************************************************
template <class T>
void Queue<T>::enqueue(T item)
{
   if (isFull())
      cout << "The queue is full.\n";
   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 <class T>
void Queue<T>::dequeue(T &item)
{
   if (isEmpty())
      cout << "The queue is empty.\n";
   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 <class T>
bool Queue<T>::isEmpty() const
{
   bool status;

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

   return status;
}

//***************************************************************
// isFull returns true if the queue is full, otherwise false.   *
//***************************************************************
template <class T>
bool Queue<T>::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 <class T>
void Queue<T>::clear()
{
   front = queueSize - 1;
   rear = queueSize - 1;
   numItems = 0;
}
#endif

//Stack.h
#ifndef STACK_H
#define STACK_H
#include <iostream>
using namespace std;

// Stack template
template <class T>
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 <class T>
Stack<T>::Stack(int size)
{
   stackArray = new T[size]; 
   stackSize = size; 
   top = -1;
}

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

template <class T>
Stack<T>::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 <class T>
Stack<T>::~Stack()
{
   if (stackSize > 0)
      delete [] stackArray;
}

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

template <class T>
void Stack<T>::push(T item)
{
   if (isFull())
   {
      cout << "The stack is full.\n";
   }
   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 <class T>
void Stack<T>::pop(T &item)
{
   if (isEmpty())
   {
      cout << "The stack is empty.\n";
   }
   else
   {
      item = stackArray[top];
      top--;
   }
}

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

template <class T>
bool Stack<T>::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 <class T>
bool Stack<T>::isEmpty()
{
   bool status;
   
   if (top == -1)
      status = true;
   else 
      status = false;
   
   return status;
}
#endif

//palindrome.h
#ifndef PALINDROME_H

#define PALINDROME_H

int isPalindrome(char *x);

#endif 

[zaphraud]

$ g++ main.cpp palindrome.cpp -o main
palindrome.cpp:4:26: fatal error: isPalindrome.h: No such file or directory
 #include "isPalindrome.h"
                          ^
compilation terminated.

Believing that to be a typo I removed the "is" and it compiled without further errors or warnings, giving me a main.exe...

~/src/forums/mysiarobin1987$ ./main
Enter a char string
nope

~/src/forums/mysiarobin1987$ ./main
Enter a char string
nun

It's running.. It's not producing any output after input however, because gets is never coming back when used that way in main.cpp - a cout statement placed right after the gets confirms this. the program dies at gets. don't use gets.

[mysiarobin1987]

i took gets out and the program still closes on me

[Enoizat]

As long as I can see, if you follow the assignment instruction, you should have a directory with these files:

Queue.h
Stack.h
palindrome.h
palindrome.cpp
main.cpp


The compilation instruction should resemble the following:
g++ -std=c++14 -Wall -Wextra -pedantic-errors palindrome.cpp main.cpp -o main.exe

In your code there’re things I can’t understand.
1) The assignment logic is pretty simple:
a) get a string
b) push every character into *both* a stack *and* a queue
c) pop back the characters from *both* the stack *and* the queue and compare them
d) since one container is FILO and the other is FIFO, what comes out is one character from the rear of the string and one from the front
e) so, if there’re no differences between the two sequences, the string was palindrome.

May I ask you what logic did you follow?

2) The assignment asks you to read a char string from console, presumably spaces included.
What instructions do you know which do that? Do you know about std::getline()?
I’ve noticed you included <string> and used std::cout...

Please consider:
in main():
- ask the user for a string
- obtain a null-terminated C-style char string from it
- pass that C-style char string to isPalindrome()
- valuate the return value

in isPalindrome():
- get the length of the passed C-style char string
- create a stack and a queue based on that length
- in a loop, check every character of the C-style char string and, if it is a letter, make it uppercase (or lowercase) and push it into the stack and the queue
- [suggestion: record the number of the pushed characters]
- once finished, start another loop, that will perform as many iteration as character you’ve pushed
- at every iteration, get back a character from the stack and one from the queue
- as soon as they don’t match, return the code for “not palindrome”
- if all them match, return code for “palindrome”
- make your life easy