The palindrome detector application will first clean and analyze a string and then inform you whether or not it is a palindrome.
This is probably one of the strangest applications I built because the requirements forced me to not make use of any header files except iostream. Thus, instead of using a string object to manipulate the palindrome, I had to use character arrays. Furthermore, the function that tests the string for a palindrome had to be a recursive function (which is a good approach actually).
But what’s a palindrome anyway? A palindrome is a sequence that reads the same in either direction.
The first two lines in the application are the typical:
#include <iostream>
using namespace std;
Next we have the function prototypes and a constant holding the initial size of the array:
// Cleans the character array
int clean(char *, int);
// Recursive function
bool isPalindrome(char *, int, int);
// Checks if the user was planning to quit
bool isQuit(char *);
// The initial size of the arrays
const int stringSize = 255;
The isPalindrome function is the recursive function that does the actual work, but first we’re going to start with the main() function:
int main()
{
char toCheck[stringSize];
char origStr[stringSize];
// Do while the user doesn’t enter ~quit
do
{
cout << “Enter palindrome: “;
cin.getline(origStr, sizeof(toCheck));
// Make a copy that will later have its spaces removed and lowercased
for(int i = 0; i < stringSize; i++)
{
toCheck[i] = origStr[i];
}
// Strip spaces and lowercase all chars
int newSize = clean(toCheck, strlen(toCheck));
// New array with new size
char newToCheck[newSize];
// Loop to fill the new array
for(int n = 0; n < newSize; n++)
{
newToCheck[n] = toCheck[n];
}
// Check if the user choosed to quit
if(isQuit(newToCheck))
{
return false;
}
// Run the function and show the result
if(isPalindrome(newToCheck, 0, newSize – 1))
{
cout << “Yes, “ << origStr << ” is a palindrome!\r\n”;
}
else
{
cout << “No, ” << origStr << ” is not a palindrome!\r\n”;
}
}
while(true);
system(“PAUSE”);
return 0;
}
The origStr array is the one that contains the original string, while toCheck will be the one that’s manipulated by being stripped of all the characters that are not numbers or uppercase/lowercase letters. This is done using the clean function that you’ll get to see right away.
The isQuit function checks if the user has entered ~quit in the command prompt, case in which it exists the application:
bool isQuit(char* phrase)
{
char quit[6] = “~quit”;
// Compare the char array to ‘~quit’
for(int i = 0; i < 5; i++)
{
if(phrase[i] != quit[i])
{
return false;
}
}
return true;
}
Obviously, using strings would have made the above function much simpler, but the purpose of this code is to not use the string.h header file. We basically loop through the array and check to see if the first 5 characters match ~quit by comparing it to a character array that actually contains the the string quit.
Let’s now review the clean function, which cleans the passed character array of all spaces and characters that are not numbers, uppercase or lowercase letters. We do this by checking the ASCII value of the characters while looping through each element in the array. If the ASCII value is not one of a number, uppercase or lowercase letter, it’s not added to the new array. We also return the size of the new array back to main().
int clean(char* phrase, int size)
{
int currChar = 0;
// Loop through the original array
for(int i = 0; i < size; i++)
{
// Only allow letters and numbers for the characters
if(((int)phrase[i] >= 48 && (int)phrase[i] <= 57) || ((int)phrase[i] >= 65 && (int)phrase[i] <= 90) || ((int)phrase[i] >= 97 && (int)phrase[i] <= 122))
{
// Lower’em
phrase[currChar] = tolower(phrase[i]);
currChar++;
}
}
// We’re out with the new number of chars
return currChar;
}
Finally there’s the last function, the one that does the hard work:
bool isPalindrome(char* phrase, int start, int end)
{
// If the nearest to the left matches its mirror character to the right
if(phrase[start] == phrase[end])
{
// If we arrived at the middle of the string (considering length can be odd or even)
if(start == end || start + 1 == end)
{
// We’re good and finished
return true;
}
else
{
// We’re good and moving on to next characters
return isPalindrome(phrase, start + 1, end – 1);
}
}
else
{
// We found two characters that don’t much, we’re out of here
return false;
}
}
This function start checking the string from both side – beginning and end – and moves one character at a time towards the middle of the string. It compares character by character to see if they are identical. For as long as a character that’s not identical is found, the function keeps calling itself. Otherwise, if non-matching characters are found, the function immediately returns false.
It’s also important to notice that from the application’s point of view there are two types of palindromes: odd in length and even in length. The ones that are even in length, such as “ABBA” have no middle character, so we compare A with A, B with B and we’re done. What about “CIVIC” though? We compare C with C, I with I, and then both our start and end variables hit the common middle character V. That’s why there is an if condition that checks wherther we arrived at the same character, case in which it returns true. It also checks to see if start + 1 is the same as end, case in which we arrived at the middle of the string, but we’re in a even length string and there’s no middle character.
That’s it with this tutorial, if you compile the application using the code above, everything should work just fine as I have tested it with (what I think are) all the possible palindrome cases. You should also be able to easily convert this application into one that uses strings instead of character arrays, although in the end you’ll still want to use an array inside the isPalindrome function, because it makes comparison between characters so easy.
