11 Replies - 5923 Views - Last Post: 27 November 2012 - 05:58 PM Rate Topic: -----

#1 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 12:59 PM

I finished a program where it takes lines from a text file and tells you if it is a palindrome or not. While it does tell you if deed or maam is a palindrome,race car and words with spaces or question marks at the end don't satisfy the program even though it is a palindrome. Can anyone tell me how to make the program skip over the special characters like !,? etc and ignore the spaces but still keep the normal format when it prints?

heres my code
#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <list>
#include <fstream>

using namespace std;



void tokenize(string &X, string separators, list<string> &words)

{                             // extracts tokens from x and puts them in list
     int length = X.length();
     int first = X.find_first_not_of(separators,0);
     
     while (first>=0 && first<length)
     {
           int last = X.find_first_of(separators,first);
           if( last<0 || last > length) last = length;
           words.push_back(X.substr(first,last-first));
           first = X.find_first_not_of(separators,last+1);
           }
}    

bool palinstring(string &line)   // returns true if line contains palindrome
{
     stack<string> S;
     queue<string> Q;
     list<string> the_words;
     string one, two;
     
     tokenize(line," ,;:",the_words);
     
     list<string>::iterator start=the_words.begin();
     list<string>::iterator stop=the_words.end();
     
     while (start != stop)
     {
           S.push(*start);
           Q.push(*start);
           start++;
           }
           
    while (!Q.empty())  // checks to see if we have a palindrome
    {
          one = S.top(); S.pop();
          two = Q.front();Q.pop();
          if(one!=two) return false;
          }
          return true;
          }
          
  int main()
  {
      string line;
      ifstream pal ("pal.txt");
      
      while (getline(pal,line))
      {
            cout << line << " <= is " ;
            if (!palinstring(line)) cout << "not ";
            cout << "a palindrome\n";
            }
            system("pause");
            return 0;
            }
                                 



and heres the output


Was it a car or a cat I saw? <= is not a palindrome
abcdefedcab <= is a palindrome
Niagara, O roar again <= is not a palindrome
Able was I ere I saw Elba <= is not a palindrome
radar <= is a palindrome
tenet <= is a palindrome
refer <= is a palindrome
deeded <= is a palindrome
no lemons, no melon <= is not a palindrome
notion <= is a palindrome
Otto <= is a palindrome
Emma <= is a palindrome
Anna <= is a palindrome
level <= is a palindrome
Madam, I'm Adam <= is not a palindrome
palindrome <= is a palindrome
racecar <= is a palindrome
salads <= is a palindrome
No, it is opposition <= is not a palindrome
read, dear <= is not a palindrome
Poor Dan is in a droop <= is not a palindrome
dented <= is a palindrome
deed <= is a palindrome




it doesn't do it right.. even if i put hello in the text file it still says it's a palindrome. any help would be appriciated

Is This A Good Question/Topic? 0
  • +

Replies To: c++ palindromes with stacks and queues. Working program but needs work

#2 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6996
  • View blog
  • Posts: 14,635
  • Joined: 16-October 07

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 01:55 PM

Your code checks strings, not letters. Single strings are always true. For more than one word, it's still just comparing words. e.g.
Adam <= is a palindrome
ba ba <= is a palindrome



You should be grabbing letters. e.g.
void tokenize(const string &X, string separators, list<char> &letters)


Though, honestly, this is overkill. Just iterate over the string one character at a time. Have a validate function that checks the char. If you want to keep it, you push it. You'll also want your chars to all be the same case.
Was This Post Helpful? 0
  • +
  • -

#3 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 03:02 PM

View Postbaavgai, on 26 November 2012 - 01:55 PM, said:

Your code checks strings, not letters. Single strings are always true. For more than one word, it's still just comparing words. e.g.
Adam <= is a palindrome
ba ba <= is a palindrome



You should be grabbing letters. e.g.
void tokenize(const string &X, string separators, list<char> &letters)


Though, honestly, this is overkill. Just iterate over the string one character at a time. Have a validate function that checks the char. If you want to keep it, you push it. You'll also want your chars to all be the same case.


It is over kill but I need to do this for my class :/ but what you said has helped alot. In the process of fixing it. Also some char have to be capital since I cant change the text file. I'll have to see if i can ignore them. Thanks a bunch by the way!
Was This Post Helpful? 0
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 03:13 PM

What he meant was that you should copy the relevant data to a new string. For example, if the string you are checking is "Was it a car or a cat I saw", then you should scan over it one letter at a time, and if it is a character, append the lowercase version of that character to the new string. So, the string you would actually check to be a palindrome is "wasitacaroracatisaw". Since this is a new string, the old one will be preserved for output.
Was This Post Helpful? 0
  • +
  • -

#5 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 03:19 PM

View Postmojo666, on 26 November 2012 - 03:13 PM, said:

What he meant was that you should copy the relevant data to a new string. For example, if the string you are checking is "Was it a car or a cat I saw", then you should scan over it one letter at a time, and if it is a character, append the lowercase version of that character to the new string. So, the string you would actually check to be a palindrome is "wasitacaroracatisaw". Since this is a new string, the old one will be preserved for output.


I understand what you mean but how would i do that in my program? do i have to put it into another stack?
Was This Post Helpful? 0
  • +
  • -

#6 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • Joined: 27-June 09

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 04:27 PM

Like Bavgai suggested, instead of "list<strin> &words", use "list<char> &letters". Alter your code so that when you populate the list, a string like "Was it a car or a cat I saw" would become the list {w,a,s,i,t,a,c,a,r,o,r,a,c,a,t,i,s,a,w}. Then, you should only have to alter the types in palinstring to work on characters instead of strings.
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6996
  • View blog
  • Posts: 14,635
  • Joined: 16-October 07

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 26 November 2012 - 05:25 PM

View Postrb26dett26, on 26 November 2012 - 05:02 PM, said:

Also some char have to be capital since I cant change the text file. I'll have to see if i can ignore them.


You don't ignore them, you convert them. Go all upper case or all lower case. Rather than checking what you shouldn't have, check for what you should have. You want only letters.
Was This Post Helpful? 0
  • +
  • -

#8 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 27 November 2012 - 08:52 AM

View Postbaavgai, on 26 November 2012 - 05:25 PM, said:

View Postrb26dett26, on 26 November 2012 - 05:02 PM, said:

Also some char have to be capital since I cant change the text file. I'll have to see if i can ignore them.


You don't ignore them, you convert them. Go all upper case or all lower case. Rather than checking what you shouldn't have, check for what you should have. You want only letters.

sweet! thanks for the huge help! This will help a lot. i'll see if i can covert them.
Was This Post Helpful? 0
  • +
  • -

#9 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 27 November 2012 - 08:55 AM

http://www.cplusplus...cctype/toupper/
Was This Post Helpful? 0
  • +
  • -

#10 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 27 November 2012 - 01:39 PM

View Postipushmycar, on 27 November 2012 - 08:55 AM, said:



I have gotten it from like 20 errors to one. Heres my code.


#include <string>
#include <stack>
#include <queue>
#include <iostream>
#include <list>
#include <fstream>


using namespace std;



void tokenize(const string &X, string separators, list<char> &letters)


{                                            // extracts tokens from x and puts them in list
     int length = X.length();
     int first = X.find_first_not_of(separators,0);
     
     while (first>=0 && first<length)
     {
           int last = X.find_first_of(separators,first);
           if( last<0 || last > length) last = length;
           letters.push_back(first,last-first);    // <------ error happening here
           first = X.find_first_not_of(separators,last+1);
           }
}    

bool palinstring(string &line)   // returns true if line contains palindrome
{
     stack<char> S;
     queue<char> Q;
     list<char> the_letters;
     char one,two;
     
     tokenize(line, " ,;:?!" ,the_letters);
     
     list<char>::iterator start=the_letters.begin();
     list<char>::iterator stop=the_letters.end();
     
     while (start != stop)
     {
           S.push(*start);
           Q.push(*start);
           start++;
           }
           
    while (!Q.empty())  // checks to see if we have a palindrome
    {
          one = S.top(); S.pop();
          two = Q.front();Q.pop();
          if(one!=two) return false;
          }
          return true;
          }
          
  int main()
  {
      string line;
      ifstream pal ("pal.txt");
      
      while (getline(pal,line))
      {
            cout << line << " <= is " ;
            if (!palinstring(line)) cout << "not ";
            cout << "a palindrome" << endl;
            }
            system("pause");
            return 0;
            }
                                 
       



and here is the error


29 C:\Users\Random\Desktop\csci 241 2012 porgrams\program6test2.cpp no matching function for call to `std::list<char, std::allocator<char> >::push_back(int&, int)'
Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 6996
  • View blog
  • Posts: 14,635
  • Joined: 16-October 07

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 27 November 2012 - 03:20 PM

Forget find_first_not_of exists. Forget length exists.

You want to iterate over every character in that string. You then decide which characters you want to push into that list. It's actually much easier than you're making it.
Was This Post Helpful? 0
  • +
  • -

#12 rb26dett26  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 26-November 12

Re: c++ palindromes with stacks and queues. Working program but needs work

Posted 27 November 2012 - 05:58 PM

View Postbaavgai, on 27 November 2012 - 03:20 PM, said:

Forget find_first_not_of exists. Forget length exists.

You want to iterate over every character in that string. You then decide which characters you want to push into that list. It's actually much easier than you're making it.

Gotcha thanks!! your help is appreciated! Working on the code now
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1