CS 202 Fall 2013  >  In-Class Challenge for Tuesday, December 3, 2013

---

CS 202 Fall 2013
In-Class Challenge for Tuesday, December 3, 2013

Our Goal

We wish to write a recursive function isPal that takes a string and determines whether it is a palindrome.

A palindrome is a string that is the same forward and backward, when only letters are counted, and upper case is considered the same as lower case. For example, the string

A man, a plan, a canal: Panama!

is a palindrome. The characters that count, all converted to lower case, are “amanaplanacanalpanama”; this reads the same forward and backward.

How do we think about this problem recursively? A string is a palindrome if any of the following is true.

• It has length at most 1. (BASE CASE)
• It begins with a non-letter, and the string obtained by throwing out the first character is a palindrome.
• It ends with a non-letter, and the string obtained by throwing out the last character is a palindrome.
• It begins and ends with the same letter (being careful about upper/lower case), and the string obtained by throwing out the first and last characters is a palindrome.

Some (Hopefully) Helpful Things

Indexing a string

An object of type string has a member function size that returns its length (the number of characters in it). Characters are numbered \(0\) to \(\mathrm{size}-1\). It also has a bracket operator.

[C++]

#include <string>
using std::string;

string s;
s.size()       // Length of s
// If s is nonempty:
s[0]           // First character in s
s[s.size()-1]  // Last character in s

Substrings

You can make a new string object containing some of the characters in an existing string by using member function substr. Passing one integer as a parameter gives the substring starting at that index and continuing to the end of the string. Passing two integers as parameters gives the substring starting at the index given by the first parameter, whose length is at most the second parameter.

[C++]

s.substr(3)     // Substring starting at index 3, continuing to end of
                //  string

s.substr(3, 6)  // Substring starting at index 3, length 6
                //  (or to end of string if this is shorter than 6)

s.substr(1)     // Substring consisting of all but first character

s.substr(0, s.size()-1)
                // Substring consisting of all but last character

Character Functions

Function isalpha. tells whether a char value is a letter, Function tolower converts a letter to lower case. Both are declared in standard header <cctype>.

[C++]

#include <cctype>
using std::isalpha;
using std::tolower;

char c;
if (isalpha(c))            // Is c a letter?
{
    char c2 = tolower(c);  // Lower-case version of c
}

What to Do

Do as many of the following as you can before class ends. After each, please show me your work.

1. Write function isPal, in header ispal.h and source file ispal.cpp. The function should be recursive. For this version, you may assume that the given strings consist only of letters, and that upper case and lower case are distinct. The resulting code should compile and pass all tests in the first test suite in test_ispal.cpp.
2. Improve function isPal so that it does things right. The resulting code should compile and pass all tests.

---