Trying to find Palindrome in a Bool Function Using Strings

[Momothegreat]

Yo guys.
I'm trying to find whether or not a word is a palindrome.

It seems like that my program is constantly returning True for all words read.
I'm not sure why.

Here's the program prompt:
Design a bool value-returning function that when passed a string will return true if the string is a palindrome.
False if it is not.
A palindrome is a sequence of characters that reads the same forward and backward.
For example, "radar", "#@, woW,@ #", and "A man a plan a canal Panama" are palindromes.
The function should ignore blanks and consider uppercase and lowercase letters the same.
Any other non-whitespace characters, digits, punctuation, etc. must match.
Assume a data file would contain one string to test per line.

Here's my code:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool check_palindrome(string, int, int&); // input are words, word count, and output is palindrome count
void format(string&, int, int&);        // formats the words to capitalize all letters and get rid of space

int main()
{

  string words;
  int wcount;  // word count
  int pcount; // palindrome count
  int n;   

  getline(cin,words); // gets the whole word per line
  while (cin)
    {
      format(words,n,wcount);
      if(check_palindrome(words,n,pcount))
	{
	  cout << words << " is a palindrome" << endl;
	}
      else
	cout << words << " is not a palindrome" << endl;
      getline(cin,words);
    }
  
}

void format(string& word, int n, int& wcount)
{
  wcount = 0;
  n = word.length();
  for (int i = 0; i < n; i++)
    {
      word[i] = toupper(word[i]); // makes all letters capital
      if(word[i] == ' ')                  // gets rid of spaces between letters
	word[i] = word[i-1];
      wcount++;
    }
}

bool check_palindrome(string word, int n, int& pcount)
{
  pcount = 0;
  n = word.length();
  for (int i = 0; i < n; i++) // starts at first position of the word and goes up by 1
    {
    for (int j = n; j >= 0; j--) // starts at end position of word and decreases by 1
      if (word[i] == word[j]) // so this should compare word[0] == word[endposition]
	{
	  return true;
	  pcount ++;
	}
    }
  return false;
}

I'm compiling with g++.
I'm using linux redirection and batch processing to feed in data.
i.e
g++ palindrome.cpp
./a.out < myfileofwords

[Peter87]

check_palindrome returns true as soon as it finds two characters that match, so a word like "Feet" would return true because the first and last e match. You probably should do it the other way around, and check for missmatches in the loop and if no missmatches was found you return true after the loop. Also note that the last character in the string is located at word[word.length() - 1] and not word[word.length()].

Your format function is not handling spaces correctly. At the moment it just overwrites the spaces with the previous character in the string, so "A man a plan a canal Panama" will become "aamannaaplannaacanallpanama".

[Momothegreat]

@Peter87
Alright thanks for the insights.
Here's my updated code:

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool check_palindrome(string, int&); // input are words, word count, and output is palindrome count
string format(string&, string&, int&); // formats the words to capitalize all letters and get rid of space; changed this into a value returning function that passes a string without spaces

int main()
{

  string words;
  int wcount;  // word count
  int pcount; // palindrome count
  string combine;

  getline(cin,words); // gets the whole word per line
  while (cin)
    {
      format(words, combine,wcount);
      if(check_palindrome(combine,pcount))
	{
	  cout << combine << " is a palindrome" << endl;
	}
      else
	cout << combine << " is not a palindrome" << endl;
      getline(cin,words);
    }
  cout << "Total words were: " << wcount << endl;
  cout << "Total palindromes were: " << pcount << endl;

  return  0;
}

string format(string& word, string& combine, int& wcount)
{
  combine=""; // creates an empty string
  int n;
  wcount = 0;
  n = word.length();
  for (int i = 0; i < n; i++)
    {
      word[i] = toupper(word[i]); // makes all letters capital
      if(word[i] != ' ')          // while there are no spaces, add to the empty string
	combine = combine + word[i];
      wcount++;
    }
  return combine;
}

bool check_palindrome(string word, int& pcount)
{
  int n;
  pcount = 0;
  n = word.length();
  for (int i = 0; i < n/2; i++) // starts at first position of the word and goes up by 1
    for (int j = n; j >= n/2; j--) // starts at end position of word and decreases by 1
      if (word[i] != word[j]) // so this should compare word[0] == word[endposition]
	{
	  return false;
	}
  pcount++;
  return true;
}

So I fixed handling white spaces.
I changed it from a void to a value returning function that adds characters to an empty string. Was there an easier way to do it?
I also edited my function for checking palindromes to make it more efficient.
I figured it doesn't need to count down from each character position from both directions but simply to the half way point.
I also changed j= n to j = n-1.
But now everything is returning false...........

Here's my input data:

pooP
Po Op
notapalindrome
radar
#@, woW,@ #
A man a plan a canal Panama
no spaceS

Here's my output data:

POOP is not a palindrome
POOP is not a palindrome
NOTAPALINDROME is not a palindrome
RADAR is not a palindrome
#@,WOW,@# is not a palindrome
AMANAPLANACANALPANAMA is not a palindrome
NOSPACES is not a palindrome
Total words were: 9
Total palindromes were: 0

[Peter87]

When you have nested loops like that, the inner loop will run it's way all way through for each iteration of the outer loop.

Put a print statement in it and you will see what I mean.

for (int i = 0; i < n/2; i++)
    for (int j = n; j >= n/2; j--)
        cout << i << " " << j << endl;

[Momothegreat]

@Peter87
Thank bru.
My j loop was decrementing but my i loop was staying at 0.
My friend told me to try a while loop so that's what I did.
I'm not sure why this works but it does.

// This program will read in sentences per line.
// It will get rid of any spaces and treat the entire line as one word.
// It will determine if the phrase in a palindrome or not and keep count.

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool check_palindrome(string); // input are words, word count, and output is palindrome count
string format(string&, string&); // formats the words to capitalize all letters and get rid of space

int main()
{

  string words;
  int wcount = 0;  // word count
  int pcount = 0; // palindrome count
  string combine;
 
  getline(cin,words); // gets the whole word per line
  while (cin)
    {
      format(words,combine);
      if(check_palindrome(combine))
	{
	  pcount++;
	  wcount++;
	  cout << combine << " is a palindrome" << endl;
	}
      else
	{
	  wcount++;
	  cout << combine << " is not a palindrome" << endl;
	}
      getline(cin,words);
    }
  cout << "Total words were: " << wcount << endl;
  cout << "Total palindromes were: " << pcount << endl;

  return  0;
}

string format(string& word, string& combine) // reads in a word; reads out a formatted word by reference
{
  int n;
  combine="";
  n = word.length();
  for (int i = 0; i < n; i++)
    {
      word[i] = toupper(word[i]); // makes all letters capital
      if(word[i] != ' ')          // gets rid of spaces between letters
	combine = combine + word[i]; // adds only characters to empty string
    }
  return combine;
}

bool check_palindrome(string word)
{
  int n;        
  n = word.length();  // find a word's length
  for (int i =0; i < n; i++)   // set up a for loop starting at position 0 and incrementing by 1
    for (int j = n-1 ; j >= 0; j--) // embedded for loop starting at end postion and decrementing by 1
      while( i < j)           // meets in a the middle position
	if (word[i] == word[j]) // if it finds a match
	  {
	    return true;
	  }
	else 
	  return false;
}

Sample Input:

pooP
Po Op
notapalindrome
radar
#@, woW,@ #
A man a plan a canal Panama
no spaceS
A but tuba
A car a man a maraca
.A dog a plan a canal pagoda.
!A dog A panic in a pagoda!

Sample Output:

POOP is a palindrome
POOP is a palindrome
NOTAPALINDROME is not a palindrome
RADAR is a palindrome
#@,WOW,@# is a palindrome
AMANAPLANACANALPANAMA is a palindrome
NOSPACES is not a palindrome
ABUTTUBA is a palindrome
ACARAMANAMARACA is a palindrome
.ADOGAPLANACANALPAGODA. is a palindrome
!ADOGAPANICINAPAGODA! is a palindrome
Total words were: 11
Total palindromes were: 9

[Peter87]

I'm not sure why this works but it does.

It only checks the first and last character. Just enter any word that start and end with the same character and it will say it's a palindrome, even if it's not.

[Momothegreat]

Peter....
god damnit man.
Can you please tell me why it doesn't go through all the iterations?

[keskiverto]

What happens on line 67?

// debug version
bool check_palindrome(string word)
{
  int n;        
  n = word.length();
  for (int i =0; i < n; i++)
    for (int j = n-1 ; j >= 0; j--)
      while( i < j)
      {
        std::cout << "i=" << i << " j=" << j << " comparing ";
        std::cout << word[i] << " and " << word[j] << '\n'
      }

 return false;
}

That should be illuminating.

[Momothegreat]

@keskiverto
Alright.
I think there are 2 problems.
The 1st problem is that my i loop should increment simultaneously while my j loop decrements.
Which is not the case. The j loop will compare each end character with the first one and only until it's finished will the i increment.

The second problem is the return statement. As soon as any letters are the same, it will stop the loop and just return True. I only want it to return true after it has checked each character.

I tried a lot of trial and error and I can't figure it out.

[keskiverto]

The second problem is the return statement. As soon as any letters are the same, it will stop the loop and just return True.

What about your line 70? No matter whether the characters are same or not, you will call return. For that reason this much simpler function produces the same result:

bool check_palindrome(string word)
{
  int n = word.length();
  int i = 0;
  int j = n - 1;
  if ( word[i] == word[j] )
  {
    return true;
  }
  else
  {
    return false;
  }
}

That is obviously not correct.

You don't want to return before you know the whole truth. Therefore, you need to store the status somewhere:

bool identical = true; // we start by assuming that word is a palindrome

// do the loop here

return identical;

The loop will compare some pairs of characters. There is asymmetry: the word is a palindrome only if all pairs are identical, but not a palindrome if any pair is not identical. That is why we start by assuming true.

A pair that is identical will not change the situation, but a mismatch will change the state to false. One can actually make it quicker and break the loop at that moment.

The 1st problem is that my i loop should increment simultaneously while my j loop decrements.

You need only one loop. Remember, that these are equivalent:

// A
int i;
for ( i = 0; i < n; ++i ) {
  // code
}

// B
int i = 0;
while ( i < n ) {
  // code
  ++i;
}

You can use the comma operator too:

for ( int i=0, j=0; i < n; ++i, --j ) {
  std::cout << i << " vs " << j << '\n';
}

[Momothegreat]

@keskiervto
Thanks so much for spending your time on this!

Here's what I did:

bool check_palindrome(string word)
{
  bool valid;	
  int n = word.length();  // find a word's length
  for ( int i=0, j=n-1; i < n; i++, j-- )
 	{
 		if (word[i] == word[j])
 		{
 		cout << i << " vs " << j << '\n';
 		valid = true;
 		}
 		else 
 		valid = false;
 	}
if(valid)
return true;
else
return false;
}

Now it seems to work for the first word read in.
But for each additional word, the counter will fk up.

For example, here's the input:

poop
ploop
pkloop

And here's the output:

0 vs 3
1 vs 2
2 vs 1
3 vs 0
POOP is a palindrome
0 vs 4
2 vs 2
4 vs 0
PLOOP is a palindrome
0 vs 5
5 vs 0
PKLOOP is a palindrome
Total words were: 3
Total palindromes were: 3

So for the word "poop"; the i count goes from 1, 2, 3 && the j count goes from 3,2,1.
But for "ploop" and for "pkloop" the counter seems to decrements by 2 in the first iteration and then by 3 in the second.
What's going on?
Or am I misunderstanding this?

[keskiverto]

Line 3: uninitialized variable. It is vital for our strategy to initialize the 'valid' correctly.

Line 5: how far should you iterate? Your 'poop' example shows that you compare every pair twice.

Line 10: Logical error.
If the previous pairs have all been identical, then the valid needs no changing.
If there has been a mismatch before, then you really should not mark the word as a palindrome.

Lines 15-18: no error, but I'll add comments to your code:

if ( valid )
{
  // We know that valid==true
  // We could write: return valid;
  return true;
}
else
{
  // We know that valid==false
  // We could write: return valid;
  return false;
}

Then the "odd ones":

PLOOP
POOLP
0 2 4

PKLOOP
POOLKP
0    5

[dhayden]

You almost have check_palindrome() working. Once it does, you will need to deal with this:

The function should ignore blanks and consider uppercase and lowercase letters the same.

Don't panic, there's an easy way to do this. Create a second string inside check_palindrome that is the input string, minus the spaces, and with all letters converted to upper case. Then check THAT string to see if it's a palindrome.

[Momothegreat]

@dhayden
ye I took care of all that in my format function, I then pass the formatted string by reference to the check palindrome function.

@keskiervto
I finally got it man.
Thanks so much!
I understand the iterations now too; it checks the first and last position, and then the second and second last position didn't match so it fell out of the loop, that's why it didn't print the counter. Also I changed the condition i < n to i <n/2; that way it doesn't check each position twice starting at both ends, but stops half way.

Here it is:

// This program will read in sentences per line.
// It will get rid of any spaces and treat the entire line as one word.
// It will determine if the phrase in a palindrome or not and keep count.

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool check_palindrome(string); // input are words, word count, and output is palindrome count
string format(string&, string&); // formats the words to capitalize all letters and get rid of space

int main()
{

  string words;
  int wcount = 0;  // word count
  int pcount = 0; // palindrome count
  string combine; // formatted string
 
  getline(cin,words); // gets the whole word per line
  while (cin)
    {
      format(words,combine);
      if(check_palindrome(combine))
	{
	  pcount++;
	  wcount++;
	  cout << combine << " is a palindrome" << endl;
	}
      else
	{
	  wcount++;
	  cout << combine << " is not a palindrome" << endl;
	}
      getline(cin,words);
    }
  cout << "Total words were: " << wcount << endl;
  cout << "Total palindromes were: " << pcount << endl;

  return  0;
}

string format(string& word, string& combine) // reads in a word; reads out a formatted word by reference
{
  int n;
  combine="";
  n = word.length();
  for (int i = 0; i < n; i++)
    {
      word[i] = toupper(word[i]); // makes all letters capital
      if(word[i] != ' ')          // gets rid of spaces between letters
	combine = combine + word[i]; // adds only characters to empty string
    }
  return combine;
}

bool check_palindrome(string word)
{
  bool valid = true;       
  //int j; // for end loop count 
  int n = word.length();  // find a word's length
  for (int i =0, j= n-1; i < n/2; i++, j--)   // set up 2 loops, one starts at position 0, the other at n.
    if (word[i] == word[j]) // if it finds a match
      valid;  // keep valid as true
    else 
      valid = false; // else valid becomes false
  return valid;
}

Sample Input:

pooP
ploop
pkloop
b o    o b
boooooobies
Po Op
notapalindrome
radar
#@, woW,@ #
A man a plan a canal Panama
no spaceS
A but tuba
A car a man a maraca
.A dog a plan a canal pagoda.
!A dog A panic in a pagoda!

Output:

POOP is a palindrome
PLOOP is not a palindrome
PKLOOP is not a palindrome
BOOB is a palindrome
BOOOOOOBIES is not a palindrome
POOP is a palindrome
NOTAPALINDROME is not a palindrome
RADAR is a palindrome
#@,WOW,@# is a palindrome
AMANAPLANACANALPANAMA is a palindrome
NOSPACES is not a palindrome
ABUTTUBA is a palindrome
ACARAMANAMARACA is a palindrome
.ADOGAPLANACANALPAGODA. is a palindrome
!ADOGAPANICINAPAGODA! is a palindrome
Total words were: 15
Total palindromes were: 10

[keskiverto]

Good.

Some notes:
1.

getline(cin,words);
while (cin)
{
  // code
  getline(cin,words);
}

Does the getline return something? If yes, what?


2.

if ( check_palindrome(combine) )
{
  wcount++;
}
else
{
  wcount++;
}

Incrementing the wcount does not seem to depend on the condition. It would be less typing to:

++wcount;
if ( check_palindrome(combine) )
{
}
else
{
}

3.

if ( word[i] == word[j] )
{
  valid; // a statement that does nothing
}
else
{
  valid = false;
}

If only one branch does something, then there is no reason to have more than that one branch.

if ( word[i] != word[j] )
{
  valid = false;
}

4.
for ( int i =0, j= n-1; i < n/2; i++, j-- )
The n/2 is okay, but so is this too:
for ( int i=0, j=n-1; i < j; ++i, --j )