C++ Palindrome help

[NinjaLink]

I recently have a thread open, but I feel it is starting to get too long, and the topic is kind of old since I have a new problem now.

What I am trying to accomplish here is determining whether a word is a palindrome using queues. My program compiles and executes fine. The only problem is that I am getting the wrong output and need some assistance. I put a bool variable isPalin, but I do not know if I am using it correctly.

Current output:

racecar is a Palindrome
123456789 is NOT a Palindrome
mom is NOT a Palindrome
dog is NOT a Palindrome
noon is NOT a Palindrome

Expected output:

racecar is a Palindrome
123456789 is NOT a Palindrome
mom is a Palindrome
dog is NOT a Palindrome
noon is 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
   int counter = 0; // declares counter
   

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


   u.initializeQueue();
   r.initializeQueue();
   s.initializeQueue();

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=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*/
      {
      u.deleteQueue();
      r.deleteQueue();
      isPalin=false;
      break;
      }
}

if (isPalin)
{
outData<<word<<" is a Palindrome"<<endl;
}
else
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

[jonsca]

Something weird is going on with your streams they are getting lumped together if your queue starts out empty

Printing pre-reverse U
From the print step
-------------------------
Printing reversed U (R)
From the print step
-------------------------
Printing pre-reverse U
From the print step
racecar
-------------------------
Printing reversed U (R)
From the print step
-------------------------
Printing pre-reverse U
From the print step
bobr
bobr
racecar
racecar
-------------------------
Printing reversed U (R)
From the print step
racecar
-------------------------

That and I don't think your reversal step is reversing at all.

[NinjaLink]

This is what I have now. I've been trying different things for hours lol. What does your last post mean? I do not understand. Is there a simple way of doing a palindrome using queues? I feel like it can't be done lol.

#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
   int counter = 0; // declares counter
   

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


   u.initializeQueue();
   r.initializeQueue();
   s.initializeQueue();

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;

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;
      outData<<word<<" is NOT a Palindrome"<<endl;
      u.deleteQueue();
      r.deleteQueue();           
      break;
      }
  else
     {
     isPalin = true;
      outData<<word<<" is a Palindrome"<<endl;
     break;
     }
}

ss.clear();

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

[jonsca]

I've been playing around with it a bit but...
So with the example "SPOON"
U queue: SPOON (the original one, you fill it back up again which gets confusing)
R queue: NOOPS (should be this way but it's not)
so you empty U out and put SPOON back into it again in the process of making R
u.first() vs. r.first() S vs N not the same, toggle your boolean and we say it's not a palindrome

"NOON"
U : NOON
R : NOON
u.first() vs. r.first() N vs. N check
Update U to OON (by your delete step)
Update R to OON
u.first vs r.first O vs. O check
etc.
boolean remains true, so it's a palindrome

But....your reversing technique is taking the front of of one queue and putting it into the back of another, so they're sharing the same order, so you're testing bobr vs. bobr instead of bobr vs. rbob. What we really need to do is get the back element of a queue (which we can), put it into another (which we can) and pop off the back element and get the next to last (which we cannot).

What I think you should do (like I had started to mention before) is split your string, so NOON would become NO and ON. Flip around ON and enqueue it as NO, now you can compare the two. If you have a string with an odd number of letters or numbers, 10001, take 10 throw out 0 and keep 01. Enqueue 01 backwards as 10 (where you can just take the last character of the string as the first and march until the middle). Phew. Anyway, I might be on later but I've got some stuff to finish up so give it a try. It won't be too much overhauling, just with the strings.

[jonsca]

This may be helpful to you if you are sticking with sstream:
http://www.cplusplus.com/reference/iostream/istream/seekg/

[NinjaLink]

The only thing is that I have no clue on what else to do with what I have because I came this far. I'm not very good at programming =/

[jonsca]

The string stream part will take the longest but it's not too big of an undertaking.
If your stream has racecar (7 chars) in it, you would start at one end of the stringstream and queue up r-a-c (up to lenght/2-1), throw away the 3rd element -e-, start a new queue and pull from character 6 (r), character 5 (a), character 4 (c) and fill it in that order. Now you have 2 queues that you can compare character by character. Now you don't have to do anymore reversing which takes out that glitch (until you get to deques in your course lol). You're doing your reversing at the string level and still obeying the rules of your queue data structure.
I hope that helps. If you've come this far you certainly have enough to see this one through to the finish. Look up the specifics for stringstream in your text or online.

[NinjaLink]

Is there a more simpler task in doing this? I feel like I am doing it a complicated way instead of doing it very simple and basic for some reason.

[jonsca]

I can't think of one but that doesn't mean anything. I did a quick net search and it's completely sensible: if you use a queue and a stack together (pushing it onto the stack and popping an element off as you pull one from the queue and comparing them). I didn't find much at all for those using queues exclusively. A double ended queue would work but that's not the specification you were given with the queue.h.
It's great if you can come up with a faster solution but it may take you more time than it would to cobble the rest of this one together.

[NinjaLink]

I have to use just queues unfortunately...This is what I have now, however, it is still giving me the wrong output.

#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
   int counter = 0; // declares counter
   

   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 = 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;
      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;
}