C++ RSS C++ RSS

C++ Palindrome help

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Mar 2008
Posts: 370
Reputation: NinjaLink is an unknown quantity at this point 
Solved Threads: 0
NinjaLink NinjaLink is offline Offline
Posting Whiz

C++ Palindrome help

 
0
  #1
22 Days Ago
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

C++ Syntax (Toggle Plain Text) 
  1. #include <fstream>
  2. #include <string>
  3. #include <sstream>
  4. #include <stdlib.h>
  5. #include "queue.h"
  6.  
  7. using namespace std;
  8.  
  9. int main() 
  10. { 
  11.  
  12.    stringstream ss;
  13.    string line; // name of my identifier used to read in data
  14.    string word; // individual characters
  15.    queueType<string> u; // declares queue u
  16.    queueType<string> r; // declare queue r
  17.    queueType<string> s; // declare queue s
  18.    int counter = 0; // declares counter
  19.  
  20.  
  21.    ifstream inData("input.txt"); // declaration of inData
  22.    ofstream outData("output.txt"); // declaration of outData
  23.  
  24.  
  25.    u.initializeQueue();
  26.    r.initializeQueue();
  27.    s.initializeQueue();
  28.  
  29. while ( getline( inData, line ) ) // reads words in file using getline to capture all spaces
  30. { /*something to break up line into individual character*/
  31.  
  32. ss << line;
  33.  
  34. while ( ss >> word )/*there are still characters*/
  35. {
  36.     u.addQueue(word);
  37.     s.addQueue(word);     /*adds characters of word into queues u and s*/
  38. }
  39.  
  40. while (!u.isEmptyQueue()) /*u is not empty*/
  41. {
  42.     r.addQueue(u.front());
  43.     u.deleteQueue();
  44.                /*adds to the front of u into r and then delete from u*/
  45. }
  46.  
  47. bool isPalin=true;
  48.  
  49. while (!s.isEmptyQueue())/*s is not empty*/
  50. {
  51.       s.deleteQueue();
  52.       u.addQueue(word);
  53.  
  54.   if(!(u.front() == r.front()))    /*compares front elements, does something if the two not equal, delete elements*/
  55.       {
  56.       u.deleteQueue();
  57.       r.deleteQueue();
  58.       isPalin=false;
  59.       break;
  60.       }
  61. }
  62.  
  63. if (isPalin)
  64. {
  65. outData<<word<<" is a Palindrome"<<endl;
  66. }
  67. else
  68. outData<<word<<" is NOT a Palindrome"<<endl;
  69.  
  70. ss.clear();
  71.  
  72. }
  73.     inData.close(); // closes inData
  74.     outData.close(); // closes outData
  75.  
  76.     system("PAUSE");
  77.     return 0;
  78. }



queue.h


C++ Syntax (Toggle Plain Text) 
  1. #ifndef H_queueType
  2. #define H_queueType
  3.  
  4. #include <iostream>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. template<class Type>
  10. class queueType // public queueADT<Type>
  11. {
  12.       public:
  13.              const queueType<Type>& operator=(const queueType<Type>&);
  14.              bool isEmptyQueue() const;
  15.              bool isFullQueue() const;
  16.              void initializeQueue();
  17.              Type front() const;
  18.              Type back() const;
  19.              void addQueue(const Type& queueElement);
  20.              void deleteQueue();
  21.              queueType(int queueSize = 100);
  22.              queueType(const queueType<Type>& otherQueue);
  23.              ~queueType();
  24.              void printQueue();
  25.              bool operator== (const queueType<Type>&);
  26.              bool operator!= (const queueType<Type>&);
  27.  
  28.       private:
  29.               int maxQueueSize;
  30.               int count;
  31.               int queueFront;
  32.               int queueRear;
  33.               Type *list;
  34.               bool isEqual(const queueType<Type>&);
  35. };
  36.  
  37. template<class Type>
  38. bool queueType<Type>::isEmptyQueue() const
  39. {
  40.      return (count == 0);
  41. }
  42.  
  43. template<class Type>
  44. bool queueType<Type>::isFullQueue() const
  45. {
  46.      return (count == maxQueueSize);
  47. }
  48.  
  49. template<class Type>
  50. void queueType<Type>::initializeQueue()
  51. {
  52.      queueFront = 0;
  53.      queueRear = maxQueueSize - 1;
  54.      count = 0;
  55. }
  56.  
  57. template<class Type>
  58. Type queueType<Type>::front() const
  59. {
  60.      assert(!isEmptyQueue());
  61.      return list[queueFront];
  62. }
  63.  
  64. template<class Type>
  65. Type queueType<Type>::back() const
  66. {
  67.      assert(!isEmptyQueue());
  68.      return list[queueRear];
  69. }
  70.  
  71. template<class Type>
  72. void queueType<Type>::addQueue(const Type& newElement)
  73. {
  74.      if (!isFullQueue())
  75.      {
  76.        queueRear = (queueRear + 1) % maxQueueSize;
  77.  
  78.        count++;
  79.        list[queueRear] = newElement;
  80.      }
  81.  
  82.      else
  83.        cout<< "Cannot add to a full queue."<<endl;
  84. }
  85.  
  86. template<class Type>
  87. void queueType<Type>::deleteQueue()
  88. {
  89.      if (!isEmptyQueue())
  90.      {
  91.        count--;
  92.        queueFront = (queueFront + 1) % maxQueueSize;
  93.      }
  94.  
  95.      else
  96.      cout <<"Cannot remove from an empty queue"<<endl;
  97.  
  98. }
  99.  
  100. template<class Type>
  101. queueType<Type>::queueType(int queueSize)
  102. {
  103.   if (queueSize <= 0)
  104.   {
  105.     cout<<"Size of the array to hold the queue must "
  106.         <<"be positive."<<endl;
  107.     cout<<"Creating an array of size 100."<<endl;
  108.  
  109.     maxQueueSize = 100;
  110.   }
  111.  
  112.   else
  113.  
  114.      maxQueueSize = queueSize;
  115.  
  116.      queueFront = 0;
  117.      queueRear = maxQueueSize - 1;
  118.      count = 0;
  119.      list = new Type[maxQueueSize];
  120. }
  121.  
  122. template<class Type>
  123. queueType<Type>::~queueType()
  124. {
  125.    delete [] list;
  126. }
  127.  
  128.  
  129. template<class Type>
  130. bool queueType<Type>::isEqual(const queueType<Type>& otherQueue) 
  131. {
  132. bool bRet = false;
  133.  
  134. if (otherQueue.maxQueueSize == maxQueueSize && otherQueue.queueFront == queueFront)
  135. {
  136. bRet = true;
  137. for (int j = 0; j < queueFront; ++j) 
  138. {
  139. if (otherQueue.list[j] != list[j]) 
  140. {
  141. // cout << "!=( " << j << ") " << otherStack.list[j] << "!=" << list[j];
  142. bRet = false;
  143. break;
  144. }
  145. }
  146. }
  147. return bRet;
  148. }
  149.  
  150. template<class Type>
  151. bool queueType<Type>::operator==(const queueType<Type>& otherQueue) 
  152. {
  153. return isEqual(otherQueue);
  154. }
  155.  
  156. template<class Type>
  157. bool queueType<Type>::operator!=(const queueType<Type>& otherQueue) 
  158. {
  159. return !isEqual(otherQueue);
  160. }
  161.  
  162.  
  163. template<class Type>
  164. void queueType<Type>::printQueue()
  165. {
  166.  
  167. for (int x = queueFront-1; x >= 0; --x)    
  168. {        
  169. cout << list[x] << '\n';    
  170. }  
  171.  
  172.  
  173. }
  174.  
  175.  
  176.  
  177. #endif
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 383
Reputation: jonsca is an unknown quantity at this point 
Solved Threads: 46
jonsca jonsca is offline Offline
Posting Whiz
 
0
  #2
22 Days Ago
Something weird is going on with your streams they are getting lumped together if your queue starts out empty

C++ Syntax (Toggle Plain Text) 
  1. Printing pre-reverse U
  2. From the print step
  3. -------------------------
  4. Printing reversed U (R)
  5. From the print step
  6. -------------------------
  7. Printing pre-reverse U
  8. From the print step
  9. racecar
  10. -------------------------
  11. Printing reversed U (R)
  12. From the print step
  13. -------------------------
  14. Printing pre-reverse U
  15. From the print step
  16. bobr
  17. bobr
  18. racecar
  19. racecar
  20. -------------------------
  21. Printing reversed U (R)
  22. From the print step
  23. racecar
  24. -------------------------

That and I don't think your reversal step is reversing at all.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 370
Reputation: NinjaLink is an unknown quantity at this point 
Solved Threads: 0
NinjaLink NinjaLink is offline Offline
Posting Whiz
 
0
  #3
22 Days Ago
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.


C++ Syntax (Toggle Plain Text) 
  1. #include <fstream>
  2. #include <string>
  3. #include <sstream>
  4. #include <stdlib.h>
  5. #include "queue.h"
  6.  
  7. using namespace std;
  8.  
  9. int main() 
  10. { 
  11.  
  12.    stringstream ss;
  13.    string line; // name of my identifier used to read in data
  14.    string word; // individual characters
  15.    queueType<string> u; // declares queue u
  16.    queueType<string> r; // declare queue r
  17.    queueType<string> s; // declare queue s
  18.    int counter = 0; // declares counter
  19.  
  20.  
  21.    ifstream inData("input.txt"); // declaration of inData
  22.    ofstream outData("output.txt"); // declaration of outData
  23.  
  24.  
  25.    u.initializeQueue();
  26.    r.initializeQueue();
  27.    s.initializeQueue();
  28.  
  29. while ( getline( inData, line ) ) // reads words in file using getline to capture all spaces
  30. { /*something to break up line into individual character*/
  31.  
  32. ss << line;
  33.  
  34. while ( ss >> word )/*there are still characters*/
  35. {
  36.     u.addQueue(word);
  37.     s.addQueue(word);     /*adds characters of word into queues u and s*/
  38. }
  39.  
  40. while (!u.isEmptyQueue()) /*u is not empty*/
  41. {
  42.     r.addQueue(u.front());
  43.     u.deleteQueue();
  44.                /*adds to the front of u into r and then delete from u*/
  45. }
  46.  
  47. bool isPalin;
  48.  
  49. while (!s.isEmptyQueue())/*s is not empty*/
  50. {
  51.       s.deleteQueue();
  52.       u.addQueue(word);
  53.  
  54.   if(!(u.front() == r.front()))    /*compares front elements, does something if the two not equal, delete elements*/
  55.       {
  56.       isPalin = false;
  57.       outData<<word<<" is NOT a Palindrome"<<endl;
  58.       u.deleteQueue();
  59.       r.deleteQueue();           
  60.       break;
  61.       }
  62.   else
  63.      {
  64.      isPalin = true;
  65.       outData<<word<<" is a Palindrome"<<endl;
  66.      break;
  67.      }
  68. }
  69.  
  70. ss.clear();
  71.  
  72. }
  73.     inData.close(); // closes inData
  74.     outData.close(); // closes outData
  75.  
  76.     system("PAUSE");
  77.     return 0;
  78. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 383
Reputation: jonsca is an unknown quantity at this point 
Solved Threads: 46
jonsca jonsca is offline Offline
Posting Whiz
 
0
  #4
22 Days Ago
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 383
Reputation: jonsca is an unknown quantity at this point 
Solved Threads: 46
jonsca jonsca is offline Offline
Posting Whiz
 
0
  #5
22 Days Ago
This may be helpful to you if you are sticking with sstream:
http://www.cplusplus.com/reference/i...istream/seekg/
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 370
Reputation: NinjaLink is an unknown quantity at this point 
Solved Threads: 0
NinjaLink NinjaLink is offline Offline
Posting Whiz
 
0
  #6
22 Days Ago
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 =/
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 383
Reputation: jonsca is an unknown quantity at this point 
Solved Threads: 46
jonsca jonsca is offline Offline
Posting Whiz
 
0
  #7
22 Days Ago
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.
Last edited by jonsca; 22 Days Ago at 12:19 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 370
Reputation: NinjaLink is an unknown quantity at this point 
Solved Threads: 0
NinjaLink NinjaLink is offline Offline
Posting Whiz
 
0
  #8
22 Days Ago
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 383
Reputation: jonsca is an unknown quantity at this point 
Solved Threads: 46
jonsca jonsca is offline Offline
Posting Whiz
 
0
  #9
22 Days Ago
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2008
Posts: 370
Reputation: NinjaLink is an unknown quantity at this point 
Solved Threads: 0
NinjaLink NinjaLink is offline Offline
Posting Whiz
 
0
  #10
22 Days Ago
I have to use just queues unfortunately...This is what I have now, however, it is still giving me the wrong output.


C++ Syntax (Toggle Plain Text) 
  1. #include <fstream>
  2. #include <string>
  3. #include <sstream>
  4. #include <stdlib.h>
  5. #include "queue.h"
  6.  
  7. using namespace std;
  8.  
  9. int main() 
  10. { 
  11.  
  12.    stringstream ss;
  13.    string line; // name of my identifier used to read in data
  14.    string word; // individual characters
  15.    queueType<string> u; // declares queue u
  16.    queueType<string> r; // declare queue r
  17.    queueType<string> s; // declare queue s
  18.    int counter = 0; // declares counter
  19.  
  20.  
  21.    ifstream inData("input.txt"); // declaration of inData
  22.    ofstream outData("output.txt"); // declaration of outData
  23.  
  24.  
  25. while ( getline( inData, line ) ) // reads words in file using getline to capture all spaces
  26. { /*something to break up line into individual character*/
  27.  
  28. ss << line;
  29.  
  30. while ( ss >> word )/*there are still characters*/
  31. {
  32.     u.addQueue(word);
  33.     s.addQueue(word);     /*adds characters of word into queues u and s*/
  34. }
  35.  
  36. while (!u.isEmptyQueue()) /*u is not empty*/
  37. {
  38.     r.addQueue(u.front());
  39.     u.deleteQueue();
  40.                /*adds to the front of u into r and then delete from u*/
  41. }
  42.  
  43. bool isPalin = true;
  44.  
  45. while (!s.isEmptyQueue())/*s is not empty*/
  46. {
  47.       s.deleteQueue();
  48.       u.addQueue(word);
  49.  
  50.   if(!(u.front() == r.front()))    /*compares front elements, does something if the two not equal, delete elements*/
  51.       {
  52.       isPalin = false;
  53.       break;  
  54.       }
  55.   else
  56.   {
  57.       u.deleteQueue();
  58.       r.deleteQueue();
  59.   }
  60.  
  61. }
  62.  
  63. if (isPalin == true)
  64. {
  65. outData<<word<<" is a Palindrome"<<endl;
  66. }
  67. if (isPalin == false)
  68. outData<<word<<" is NOT a Palindrome"<<endl;
  69.  
  70. ss.clear();
  71.  
  72. }
  73.     inData.close(); // closes inData
  74.     outData.close(); // closes outData
  75.  
  76.     system("PAUSE");
  77.     return 0;
  78. }
Last edited by NinjaLink; 22 Days Ago at 1:03 am.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array arrays based beginner binary c++ c/c++ calculator char char* class classes code compile compiler console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news number numbertoword output parameter pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC