I am trying to determine if a word is a palindrome or not using queues, but I am receiving the wrong results. I have tried several things to get it to work using the boolean variable isPalin. Will someone lead me to the right direction please? I have been trying for hours, and I feel that it is something small that is holding me back.


Current Output:

mom is a Palindrome
cat is a Palindrome
noon is a Palindrome
mouse is a Palindrome


Expected Output


mom is a Palindrome
cat is NOT a Palindrome
noon is a Palindrome
mouse is NOT a Palindrome


main.cpp

#include <fstream>
#include <string>
#include <sstream>
#include <stdlib.h>
#include "queue.h"

using namespace std;

int main() 
{ 

   stringstream ss;
   string line; // name of my identifier used to read in data
   string word; // individual characters
   queueType<string> u; // declares queue u
   queueType<string> r; // declare queue r
   queueType<string> s; // declare queue s
   

   ifstream inData("input.txt"); // declaration of inData
   ofstream outData("output.txt"); // declaration of outData


while ( getline( inData, line ) ) // reads words in file using getline to capture all spaces
{ /*something to break up line into individual character*/

ss << line;

while ( ss >> word )/*there are still characters*/
{
    u.addQueue(word);
    s.addQueue(word);     /*adds characters of word into queues u and s*/
}

while (!u.isEmptyQueue()) /*u is not empty*/
{
    r.addQueue(u.front());
    u.deleteQueue();
               /*adds to the front of u into r and then delete from u*/
}

bool isPalin;
isPalin = true;

while (!s.isEmptyQueue())/*s is not empty*/
{
      s.deleteQueue();
      u.addQueue(word);
      
  if(!(u.front() == r.front()))    /*compares front elements, does something if the two not equal, delete elements*/
      {
      isPalin = false;
      u.deleteQueue();
      r.deleteQueue();
      break;  
      }
  else
  {
      u.deleteQueue();
      r.deleteQueue();
  }

}

if (isPalin == true)
{
outData<<word<<" is a Palindrome"<<endl;
}
if (isPalin == false)
outData<<word<<" is NOT a Palindrome"<<endl;

ss.clear();

}
    inData.close(); // closes inData
    outData.close(); // closes outData
    
    system("PAUSE");
    return 0;
}

queue.h

#ifndef H_queueType
#define H_queueType

#include <iostream>
#include <cassert>

using namespace std;

template<class Type>
class queueType // public queueADT<Type>
{
      public:
             const queueType<Type>& operator=(const queueType<Type>&);
             bool isEmptyQueue() const;
             bool isFullQueue() const;
             void initializeQueue();
             Type front() const;
             Type back() const;
             void addQueue(const Type& queueElement);
             void deleteQueue();
             queueType(int queueSize = 100);
             queueType(const queueType<Type>& otherQueue);
             ~queueType();
             void printQueue();
             bool operator== (const queueType<Type>&);
             bool operator!= (const queueType<Type>&);
             
      private:
              int maxQueueSize;
              int count;
              int queueFront;
              int queueRear;
              Type *list;
              bool isEqual(const queueType<Type>&);
};

template<class Type>
bool queueType<Type>::isEmptyQueue() const
{
     return (count == 0);
}

template<class Type>
bool queueType<Type>::isFullQueue() const
{
     return (count == maxQueueSize);
}

template<class Type>
void queueType<Type>::initializeQueue()
{
     queueFront = 0;
     queueRear = maxQueueSize - 1;
     count = 0;
}

template<class Type>
Type queueType<Type>::front() const
{
     assert(!isEmptyQueue());
     return list[queueFront];
}

template<class Type>
Type queueType<Type>::back() const
{
     assert(!isEmptyQueue());
     return list[queueRear];
}

template<class Type>
void queueType<Type>::addQueue(const Type& newElement)
{
     if (!isFullQueue())
     {
       queueRear = (queueRear + 1) % maxQueueSize;
       
       count++;
       list[queueRear] = newElement;
     }
     
     else
       cout<< "Cannot add to a full queue."<<endl;
}

template<class Type>
void queueType<Type>::deleteQueue()
{
     if (!isEmptyQueue())
     {
       count--;
       queueFront = (queueFront + 1) % maxQueueSize;
     }
     
     else
     cout <<"Cannot remove from an empty queue"<<endl;
     
}

template<class Type>
queueType<Type>::queueType(int queueSize)
{
  if (queueSize <= 0)
  {
    cout<<"Size of the array to hold the queue must "
        <<"be positive."<<endl;
    cout<<"Creating an array of size 100."<<endl;
    
    maxQueueSize = 100;
  }
  
  else
  
     maxQueueSize = queueSize;
     
     queueFront = 0;
     queueRear = maxQueueSize - 1;
     count = 0;
     list = new Type[maxQueueSize];
}

template<class Type>
queueType<Type>::~queueType()
{
   delete [] list;
}


template<class Type>
bool queueType<Type>::isEqual(const queueType<Type>& otherQueue) 
{
bool bRet = false;

if (otherQueue.maxQueueSize == maxQueueSize && otherQueue.queueFront == queueFront)
{
bRet = true;
for (int j = 0; j < queueFront; ++j) 
{
if (otherQueue.list[j] != list[j]) 
{
// cout << "!=( " << j << ") " << otherStack.list[j] << "!=" << list[j];
bRet = false;
break;
}
}
}
return bRet;
}

template<class Type>
bool queueType<Type>::operator==(const queueType<Type>& otherQueue) 
{
return isEqual(otherQueue);
}

template<class Type>
bool queueType<Type>::operator!=(const queueType<Type>& otherQueue) 
{
return !isEqual(otherQueue);
}


template<class Type>
void queueType<Type>::printQueue()
{
     
for (int x = queueFront-1; x >= 0; --x)    
{        
cout << list[x] << '\n';    
}  
     
     
}



#endif

It seems to me that you are over complicating things. Wouldn't it be a lot simpler to just use a double ended queue, otherwise known as a deque?
Modifying your code from one of your previous posts in another thread:

//Implement the palindrome-recognition algorithm described in "Simple Applications of the ADT Queue"

#include <iostream>
#include <string>
#include <deque>

using namespace std;

void isPal(string);

void isPal(string s)
{	
	deque<char> aDeque;

	for(unsigned i = 0; i < s.length(); i++)
	{	
		aDeque.push_back(s[i]);
	}
	
	bool charEqual = true;
	
	while (!aDeque.empty() && charEqual==true)
	{
		if(aDeque.front() == aDeque.back())
		{
			aDeque.pop_front();
			// as long as the pop_front() didn't empty the deque..
			if(!aDeque.empty()) 
				aDeque.pop_back(); // do a  pop_back()
		}
		else
			charEqual=false;
	}
	
	cout << word;
	if(charEqual == true)
		cout <<  " is a Palindrome" << endl;
	else
		cout << " is NOT a Palindrome" << endl;
}

int main ()
{
	string input;
	cout << "Enter the string: ";
	cin >> input;
	isPal(input);

    return 0;
}

Isn't that a lot cleaner and quicker than using two queues? it certainly saves you from creating that unneccessary template nonsense in queue.h!

EDIT:
Now modifying the above code to read words/lines from a file and then pass each word/line to the isPal() function you get this:

//Implement the palindrome-recognition algotithm described in "Simple Applications of the ADT Queue"

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <deque>

using namespace std;

bool isPal(string);

bool isPal(string s)
{	
	deque<char> aDeque;

	for(unsigned i = 0; i < s.length(); i++)
	{	
		aDeque.push_back(s[i]);
	}

	while (!aDeque.empty())
	{
		if(aDeque.front() == aDeque.back())
		{
			aDeque.pop_front();
			// as long as the pop_front didn't empty the deque..
			if(!aDeque.empty()) 
				aDeque.pop_back(); // do a  pop_back()
		}
		else
			return false;
	}
	return true;
}

int main ()
{
	ifstream inData("input.txt");
	ofstream outData("output.txt");

	stringstream ss;
	string line, word;

	while(getline(inData, line))
	{
		ss << line;

		while(ss>>word)
		{
			if(isPal(word))
				outData << word << " is a palindrome" << endl;
			else
				outData << word << " is NOT a palindrome" << endl;
		}
		word.clear();
		ss.clear();
	}
	inData.close();
	outData.close();

	return 0;
}

Cheers for now,
Jas.

Edited 7 Years Ago by JasonHippy: n/a

Jason, thank you very much sir.

I have a question...If I decide to use my queue.h, will I be able to accomplish the same thing? or is it no way that I can determine a palindrome with what I have?

I tried to use the format above using my queue class to see if it would work, but it gave the output results....

mom is a palindrome
cat is NOT a palindrome
noon is NOT a palindrome
mouse is NOT a palindrome


is there a reason why it didn't work with my queue class? Thanks

#include <fstream>
#include <sstream>
#include <string>
//#include <deque>
#include "queue.h"


using namespace std;


bool isPal(string);


bool isPal(string s)
{ 
queueType<char> aDeque;


for(unsigned i = 0; i < s.length(); i++)
{ 
aDeque.addQueue(s[i]);
}


while (!aDeque.isEmptyQueue())
{
if(aDeque.front() == aDeque.back())
{
aDeque.deleteQueue();
// as long as the pop_front didn't empty the deque..
if(!aDeque.isEmptyQueue()) 
aDeque.deleteQueue(); // do a pop_back()
}
else
return false;
}
return true;
}
int main ()
{
ifstream inData("input.txt");
ofstream outData("output.txt");
stringstream ss;
string line, word;
while(getline(inData, line))
{
ss << line;
while(ss>>word)
{
if(isPal(word))
outData << word << " is a palindrome" << endl;
else
outData << word << " is NOT a palindrome" << endl;
}
word.clear();
ss.clear();
}
inData.close();
outData.close();
return 0;
}

Is there a way I can use a pop back like you did with aDeque.pop_back(); that I can use in my last post using my queue.h

if(aDeque.front() == aDeque.back())		
{			
aDeque.pop_front();	
if(!aDeque.empty()) 			
aDeque.pop_back(); // do a  pop_back()		
}

Oh I see you've HAD to implement your own queue class as a part of your assignment...sorry I thought you were just over complicating things for yourself.

In that case, to turn your class into a double ended queue I guess you'd need to implement a function to allow the removal of items from the back of the queue, something like this perhaps?

template<class Type>
void queueType<Type>::deleteBackOfQueue()
{
     if (!isEmptyQueue())
     {
       count--;
       queueRear = (queueRear - 1) % maxQueueSize;
     }
     
     else
     cout <<"Cannot remove from an empty queue"<<endl;
     
}

Then in the if statement:

if(aDeque.front() == aDeque.back())		
{			
	aDeque.deleteQueue();	
	if(!aDeque.empty()) 			
		aDeque.deleteBackOfQueue(); // pop the back()		
}

I've not compiled or tested the above code snippets, but I'd imagine that you would need to be doing something similar to the above!

Cheers for now,
Jas.

Thank you a lot. It worked. I am VERY happy...I can't express how much I am grateful. Mission completed!

This question has already been answered. Start a new discussion instead.