EvilZone
Programming and Scripting => C - C++ => : kenjoe41 June 06, 2014, 09:59:14 PM
-
I recently had a boring nite and decided to do this simple Palindrome[http://en.wikipedia.org/wiki/Palindrome (http://en.wikipedia.org/wiki/Palindrome)] challenge. I remember doing it in python a year or two back but never did it in c++. I tried to do it in every solution that came to mind.
First obvious solution:
bool IsPalindrome(string input)
{
for(int k = 0; k < input.size() / 2; ++k)
if(input[k] != input[input.length() - 1 – k])
return false;
return true;
}
Then i said, the STL could do better. So....
bool IsPalindrome(string input)
{
string reversed = input;
reverse(input.begin(), input.end());
return reversed == input;
}
But that could be inefficient since we have to creat a copy of the string. Back to the for loop solution, probably with an iterator. Oh hail reverse_iterator.
bool IsPalindrome(string input)
{
return equal(input.begin(), input.begin() + input.size() / 2, input.rbegin());
}
Well, those are all beautiful but they all don't care to remove space and punctuation marks. Thus a sentence like, "Mr. Owl ate my metal worm" won't be a palindrome yet it is.
.......skipping some other steps here....
bool IsNotAlphaOrSpace(char ch)
{
return !isalpha(ch) && !isspace(ch);
}
bool IsWordPalindrome(string input)
{
input.erase(remove_if(input.begin(), input.end(), IsNotAlphaOrSpace), input.end());
transform(input.begin(), input.end(), input.begin(), ::toupper);
stringstream tokenizer(input);
vector<string> tokens;
tokens.insert(tokens.begin(), istream_iterator<string>(tokenizer), istream_iterator<string>());
return equal(tokens.begin(), tokens.begin() + tokens.size() / 2, tokens.rbegin());
}
I hate boring nights but it was a fun night in the algorithm land and the beautiful STL.
-
In the first one you're mixing signed and unsigned datatypes. Here's a way to do it manually:
#include <iostream>
#include <string>
using namespace std;
template <class Iter>
bool is_palindrome( Iter first, Iter last )
{
while ( ( first != last ) && ( first != --last ) )
{
if ( *first != *last ) return false;
++first;
}
return true;
}
int main()
{
string s( "123210" );
bool palindrome = is_palindrome( s.begin(), s.end() );
cout << ( palindrome ? "Palindrome!" : "Not a palindrome..." ) << endl;
}
The beauty of this over yours is that I'm not limiting this to strings, and I can choose sections of the string based on the iterator positions.
I don't need the explanation, but perhaps more explanation would help others understand the code you're posting, otherwise what's the purpose of this thread? You didn't explain that the stream you're using for the string by default delimits by spaces, so nobody is going to understand how any of that works unless they already know how it works, in which case this thread would be of no benefit to the more experienced programmers either. I'm just saying.