String Examples

We need to work through a problem involving strings that is a bit more involved than the simple example we worked on last time. How about writing a “palindrome” checker.

What is a palindrome?

A palindrome is a word or phrase that is the same forwards and backwards. A simple example of one is “anna”. A classic example is “Able I was ere I saw Elba”.

Now, we cannot simply reverse the sequence of characters and see the palindrome. What we need to do is check that the letters of the test string are identical forwards and backwards. So, how do we do this?

Support functions

To check if a given string is a palindrome, we need to change all the letters in the string to lower case, then get rid of things like punctuation or spaces. After doing all of that, we need to reverse the string and compare it to the original to see if they are equal!

Here is some code that could confirm if a sample string is a palindrome:

bool check_palindrome(string str) {
    string s1, s2, s3;
    s1 = strip_extra(lower_case(str));
    s2 = strip_extra(lower_case(reverse(str)));
    return s1 == s2;
}

Here, we have introduced a few supporting functions that take an input string and return a modified output string:

  • strip_extra - removes non letter characters
  • lower_case - returns the input string converted to lower case
  • reverse - returns the input string reversed.

This is simple. Here is a program that we might use to test our ideas:

int main(int argc, char **argv) {
    string lcstr;
    string reversed;
    string strippedstr;

    for(int i=0;i<5;i++) {
        cout << "\"" << testset[i] << "\"";
        if(check_palindrome(testset[i]))
            cout << " is a ";
        else
            cout << " is not a ";
        cout << "palindrome" << endl;
    }
}

In this chunk of code, we assume we have setup an array of test strings, and we want to output the string and a statement indicating if that string is, or is not, a palindrome.

Example strings

I did what everyine is expected to do today, Googled for a few Palindromes! This is what I got:

string testset[5] = {
    "A Toyota's a Toyota",
    "Able was I ere I saw Elba",
    "A Santa at NASA",
    "Are we not drawn onward to new era",
    "This is not a palindrome"
};

The supporting routines

All we need to do to complete this project is to build our supporting routines.

lower_case()

Let’s start off with an easy one, converting to lower case. Here is the code we need:

string lower_case(string str) {
    int len = str.size();
    string out = "";
    for(int i=0;i<len;i++)
        out.append(1,tolower(str[i]));
    return out;
}

To build this routine, I needed to search the documentation for the string class and see what functions (or methods as they are properly called) are available. I decided that the easy way to build the final string I want would be to create an empty string, then add (append) a single character at a time, converting that character to lower case as required. There is a nice C++ function I can use to do this: tolower(), which takes a single character and returns the lower case version of that character. It is smart enough not to try to lower case numbers or punctuation, so this code will do what we need!

strip_extra()

Using this same pattern, we can strip the string of unwanted characters. All we need to do here is check each character to make sure it is a letter. I am going to assume that we only call this function after we lower case all the letters in the string This is the code I ended up with:

string strip_extra(string str) {
    int len = str.size();
    char c;
    string out = "";
    for(int i=0;i<len;i++) {
        c = str[i];
        if(c >='a' && c <='z') 
            out.append(1,str[i]);
    }
    return out;
}

reverse()

The last function we need takes an input string and returns that string in reverse. Once again, we use the same pattern to build up the output string. We use a for-loop that indexes the string in reverse to get this done. Here is the code:

string reverse(string str) {
    int len = str.size();
    char c;
    string out = "";
    for(int i=0;i<len;i++) {
        c = str[len-i-1];
        out.append(1,c);
    }
    return out;
}

Wrappin up

Here is the complete program:

// Palindrome.cpp - checks a series of palindromes

# include <iostream>
using namespace std;

string testset[5] = {
    "A Toyota's a Toyota",
    "Able was I ere I saw Elba",
    "A Santa at NASA",
    "Are we not drawn onward to new era",
    "This is not a palindrome"
};

string lower_case(string);
string strip_extra(string);
string reverse(string);
bool check_palindrome(string);

int main(int argc, char **argv) {
    string lcstr;
    string reversed;
    string strippedstr;

    for(int i=0;i<5;i++) {
        cout << "\"" << testset[i] << "\"";
        if(check_palindrome(testset[i]))
            cout << " is a ";
        else
            cout << " is not a ";
        cout << "palindrome" << endl;
    }
}

bool check_palindrome(string str) {
    string s1, s2, s3;
    s1 = strip_extra(lower_case(str));
    s2 = strip_extra(lower_case(reverse(str)));
    return s1 == s2;
}

string lower_case(string str) {
    int len = str.size();
    string out = "";
    for(int i=0;i<len;i++)
        out.append(1,tolower(str[i]));
    return out;
}

string strip_extra(string str) {
    int len = str.size();
    char c;
    string out = "";
    for(int i=0;i<len;i++) {
        c = str[i];
        if(c >='a' && c <='z') 
            out.append(1,str[i]);
    }
    return out;
}

string reverse(string str) {
    int len = str.size();
    char c;
    string out = "";
    for(int i=0;i<len;i++) {
        c = str[len-i-1];
        out.append(1,c);
    }
    return out;
}

Hee is the output produced by this code:

"A Toyota's a Toyota" is a palindrome
"Able was I ere I saw Elba" is a palindrome
"A Santa at NASA" is a palindrome
"Are we not drawn onward to new era" is a palindrome
"This is not a palindrome" is not a palindrome