Palindrome Tester

NathanOliver 3 Tallied Votes 325 Views Share

Hey all

I have seen a lot of stuff about palindrome checkers so I thought I would write one that works for STL containers as well as arrays. it accepts a bidirectional iterator to the first element and an bidirectional iterator to 1 after the last element. Included is a sample of it working with a string and a vector of int's. At most this function requires O N/2 iterations(correct me please if I'm wrong). Also I chose for single characters to be considered a palindrome. I hope you guys will find this useful.

// Palindrome.h
// start points to the beginning of the data and end points to one past the end
template<typename BidirectionalIterator>
bool IsPalindrome(BidirectionalIterator start, BidirectionalIterator end)
{
	if (start == end - 1)
		return true;
	end--;
	while (start <= end)
	{
		if (*start == *end)
		{
			start++;
			end--;
		}
		else
			return false;
	}
	return true;
}



//Main.cpp
#include <iostream>
#include <string>
#include <vector>
#include "Palindrome.h"

using namespace std;

ostream & operator<<(ostream &, vector<int> &);

int main()
{
	string word = "tattarrattat";  // longest palindrome in English
	vector<int> number;
	for (int i = 0; i < 5; i++)
		number.push_back(i);
	for (int j = 4; j >= 0; j--)
		number.push_back(j);
	if (IsPalindrome(word.begin(), word.end()))
		cout << word << " is a palindrome.\n";
	else
		cout << word << " is not a palindrome.\n";
	if (IsPalindrome(number.begin(), number.end()))
		cout << number << " is a palindrome.";
	else
		cout << number << " is not a palindrome.";
	cin.get();
	return 0;
}

ostream & operator<<(ostream & stream, vector<int> & vec)
{
	for(int i = 0; i < vec.size(); i++)
		cout << vec[i];
	return stream;
}
mrnutty 761 Senior Poster

Nice post. Although I would have done some things different, the idea
is good.

NathanOliver 429 Veteran Poster Featured Poster

What would you have done differently? I am open to any and all suggestions.

Member Avatar for iamthwee
iamthwee

Why have you hard coded the numbers 5 and 4?

NathanOliver 429 Veteran Poster Featured Poster

I hard coded them just to show that you can use a vector as well. It was just an example.

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster

Instead of using two for-loops to load the vector with data, you could also do:

int arr[] = {1,2,3,2,1};
vector<int> number(arr, arr + 5);

Just a tip though.

NathanOliver 429 Veteran Poster Featured Poster

Thanks Nick I did not know a vector could be inialized that way..

mrnutty 761 Senior Poster

What would you have done differently? I am open to any and all suggestions.

Well you can make your code more concise.

template<typename StartItr, typename EndItr>
bool isPalin(StartItr start,EndItr end){
	assert(start <= end);		
	if(start == --end) return true;
	while(start < end && *start++ == *end--) continue;
	return (*--start == *++end);
}

But one might be able to program this using metaprograming technique, and
be able to find out whether an input is a palindrome during compile time.

DevonMcC++ 0 Newbie Poster

If you start adding examples, it quickly becomes apparent that there is a fair amount of repetitious code in the presentation of results which could be factored out. Also, you should probably show the negative case as well.

So, if you have something like:

template<typename StartItr, typename EndItr, typename Item>
bool checkIfPal(StartItr start, EndItr end, Item item)
{   bool rc=1;
    cout << item << " is";
    if (!isPalindrome(start, end))
    {   cout << " not";
        rc=0;
    }
    cout << " a palindrome.\n";
    return rc;
}

You could more easily add an example like this:

int arrNotP[] = {1,2,3,99,1};
    vector<int> num1(arrNotP, arrNotP + 5);
    checkIfPal(num1.begin(), num1.end(), num1);
mrnutty 761 Senior Poster

You pass num1 which is a vector of ints, and you pass its start position and its end
position, thats redundant. Makes the user do extra code. And you can't print a vector
using operator<< without defining the operator<<.

Bench 212 Posting Pro

This seems somewhat unnecessary to me - the STL will already do this for any container which supports bidirectional iterators - all of those containers support begin/end and rbegin/rend, so you can use the std::equal algorithm

#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

int main()
{
    std::string str("level");
    std::vector<char> vec(str.begin(), str.end());

    if ( std::equal(str.begin(), str.end(), str.rbegin()) )
        std::cout << "str is a palindrome" << std::endl;

    if ( std::equal(vec.begin(), vec.end(), vec.rbegin()) )
        std::cout << "vec is a palindrome" << std::endl;
}
arkoenig 340 Practically a Master Poster

I hate to rain on people's parades, but the original post says that it requires a bidirectional iterator. In fact, the code does <= comparisons on iterators--which means that it really requires random-access iterators.

NathanOliver commented: Thanks +2
NathanOliver 429 Veteran Poster Featured Poster

You are right with that arkoenig. I didn't realize that <= wasn't supported by bidirectional iterators.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.