c++ palindrome function help?

Question

Hello everyone!

I've been working on this code for a while, I almost have it running I think, my last problem is how to make a boolean function that determines if a string is an imperfect palindrome.


An imperfect palindrome is a word, verse, or sentence that is the same when read backward or forward after the removal of all whitespace and punctuation and all alphabetic characters have been folded to the same case.
ie: racecar, boob, radar


here are all my functions thus far:
http://ideone.com/gb3uJe

and here is my main() :
http://ideone.com/qffnNP



Thanks for any help! This one has been tough for me and I really appreciate any help, if you decide to help please explain in detail so I can understand too!

Thank you

Answer 1

It looks like you're trying to define the isPalindrome() function in a header file, and that header file begins with the #ifdef guard against being included twice, but never ends that #ifdef with an #endif directive. Even after you supply the missing #endif at the end, and move on two whether or not the iterator and string handling in your function logic is correct, that's a bad idea.



You should put the function definition in a .cpp file and only have the prototype in the .h file. A prototype is just a function header without the body, and that's how a "header file" got its name...it's a file of function headers only. Plus other pure non-code-generating declarations like classes, structs, enums and #define'd macros.



So the header file should just be:



#ifndef LAB55_H

#define LAB55_H



#include



bool isPalindrome(std::string s);



#endif



That's it...nothing more, except maybe comments.



Note the std::string. Don't use "using" declarations in header files. There's no way to undo a "using namespace std;" statement, so you'd be forcing that on every user of your function. Also, it's a lot of typing to just avoid just one "std::' qualifier.



Then create an ispalindrome.cpp file with:



#include

#include

#include

#include "lab55.h"



using namespace std; // if you are going to use it, put it after all includes.



...followed by your functions. Notice that this uses the very same header as the calling program will use. That keeps both parties using the same declaration of what isPalindrome is supposed to be.



Note that should be included is your are going to use isspace(), tolower(), etc. Don't depend on another header to do that for you. Another compiler, with different implementation quirks, may choke on your code.



Finally, not the use of quotes instead of <> brackets around a locally-defined header. A few compilers will need that to search the local directory for the file instead of just "standard places".



---------------------



As for isPalindrome itself, you seem to be doing a lot of extra work.



You should be able to test in place without modifying or copying the original string. In fact, I'd emphasize that fact by making the string argument a const reference:



bool isPalindrome(const &s);



The & will prevent the caller from copying the whole string onto the stack and the const will prevent isPalindrome from making any changes to the original string that's being passed now by reference.



Then, I like indexed access better than iterators on this problem because I can let them go out of bounds on edge cases without diving deep into the iterator docs to see what happens when s.begin() is decremented.



for (int i=0, j=(int)s.length()-1; i
{

.... while (i < j && !islalpha(s[i]) { ++i; }

.... while (i < j && !isalpha(s[j]) { --j; }

.... if (i < j && tolower(s[i]) != tolower(s[j])) { return false; }

}

return true;



That simply skips any non-letters on the left, then skips any non-letters on the right, then if the index values haven't collided, the lowercase conversions are compared. I used !isalpha() instead of isspace() plus a punctuation test. Basically, all non-letters are ignored equally.



The < operators inside the loop could be != operators instead. However, it's crucial that the for loop condition be < instead of != to handle an even number of letters, as in "boob".



The i


However, your functions to remove spaces and uppercase a string are useful enough that, only adding that "removePuntuation" makes for an even simpler isPalindome:



bool isPalindrome(const string &s)

{

string t = uppercase(removePunctuation(removeWhitespace(s)));

return t == stringReverse(t);

}



You'll need to either add prototypes for those subfunctions (to the .h file, maybe, since they are general-purpose) or move isPalindrome below all of those functions, so that the signatures are known.



However, that ends up making five copies of the original string, plus does twice the number of comparisons as are needed when the string really is a palindrome.

Answer 2

Not at all hard, but you should do your own homework.

First you decide how many chars you have to check, and that would be the length of the string, divided by 2.

If there is an odd nuber of letters, you don't have to check the middle one anyway.

Then you need a for loop.

You use 2 indexes.

One starts at 0 and increased up the string, while the other starts at the length and decreases.

Then inside the loop you compare the char at the first index with the char at the second index.

If they are not equal, then you change the flag initialize to true at first, to false.

When when the for loop is all done, if the flag was ever changed to false, you know it is not a palendrome.



The part where you first remove spaces, punctuation, and make all the same case, is not trivial, but you should be able to do that.

Answer 3

Learn more on persona handling in C++. A "char" just isn't a string; a char is just an persona like 'A' or 'f'. Aside from that main issue, your app has a number of syntax blunders. In line 4 you say: char rev(char ch) //you're lacking a semicolon if you want to reverse a string, the prototype of your rev perform should be something like: char* rev(char* result, const char* ch); Anyway, for your definition of 'rev' you missed the return sort.

Answer 4

To remove whitespace and punctuation, you can use the standard erase-remove idiom, and to uppercase the whole string, for_each or transform:



#include

#include

bool isPalindrome(std::string s)

{

     s.erase( remove_if(s.begin(), s.end(), [](char c){

               return std::isspace(c) || std::ispunct(c);

          }), s.end());

     for_each(s.begin(), s.end(), [](char& c) { c = std::toupper(c); });

     return equal(s.begin(), s.begin() + s.size()/2, s.rbegin());

}

int main()

{

     std::cout << std::boolalpha << isPalindrome("ab, BA") << '\n';

     std::cout << std::boolalpha << isPalindrome("not it") << '\n';

}



online demo: http://ideone.com/JSCg3w