This chapter is from the book
This chapter is from the book
This chapter is from the book
18.7 Examples: palindrome
Enough technical examples! Let’s try a little puzzle. A palindrome is a word that is spelled the same from both ends. For example, anna, petep, and malayalam are palindromes, whereas ida and homesick are not. There are two basic ways of determining whether a word is a palindrome:
- Make a copy of the letters in reverse order and compare that copy to the original.
- See if the first letter is the same as the last, then see if the second letter is the same as the second to last, and keep going until you reach the middle.
Here, we’ll take the second approach. There are many ways of expressing this idea in code depending on how we represent the word and how we keep track of how far we have come with the comparison of characters. We’ll write a little program that tests whether words are palindromes in a few different ways just to see how different language features affect the way the code looks and works.
18.7.1 Palindromes using string
First, we try a version using the standard library string with int indices to keep track of how far we have come with our comparison:
bool is_palindrome(const string& s)
{
int first = 0; // index of first letter
int last = s.length()–1; // index of last letter
while (first < last) { // we haven’t reached the middle
if (s[first]!=s[last]) return false;
++first; // move forward
––last; // move backward
}
return true;
}
We return true if we reach the middle without finding a difference. We suggest that you look at this code to convince yourself that it is correct when there are no letters in the string, just one letter in the string, an even number of letters in the string, and an odd number of letters in the string. Of course, we should not just rely on logic to see that our code is correct. We should also test. We can exercise is_palindrome() like this:
int main()
{
for (string s; cin>>s; ) {
cout << s << " is";
if (!is_palindrome(s)) cout << " not";
cout << " a palindrome\n";
}
}
Basically, the reason we are using a string is that “strings are good for dealing with words.” It is simple to read a whitespace-separated word into a string, and a string knows its size. Had we wanted to test is_palindrome() with strings containing whitespace, we could have read using getline() (§11.5). That would have shown ah ha and as df fd sa to be palindromes.
18.7.2 Palindromes using arrays
What if we didn’t have strings (or vectors), so that we had to use an array to store the characters? Let’s see:
bool is_palindrome(const char s[], int n)
// s points to the first character of an array of n characters
{
int first = 0; // index of first letter
int last = n–1; // index of last letter
while (first < last) { // we haven’t reached the middle
if (s[first]!=s[last]) return false;
++first; // move forward
––last; // move backward
}
return true;
}
To exercise is_palindrome(), we first have to get characters read into the array. One way to do that safely (i.e., without risk of overflowing the array) is like this:
istream& read_word(istream& is, char* buffer, int max)
// read at most max–1 characters from is into buffer
{
is.width(max); // read at most max–1 characters in the next >>
is >> buffer; // read whitespace-terminated word,
// add zero after the last character read into buffer
return is;
}
Setting the istream’s width appropriately prevents buffer overflow for the next >> operation. Unfortunately, it also means that we don’t know if the read terminated by whitespace or by the buffer being full (so that we need to read more characters). Also, who remembers the details of the behavior of width() for input? The standard library string and vector are really better as input buffers because they expand to fit the amount of input. The terminating 0 character is needed because most popular operations on arrays of characters (C-style strings) assume 0 termination. Using read_word() we can write
int main()
{
constexpr int max = 128;
for (char s[max]; read_word(cin,s,max); ) {
cout << s << " is";
if (!is_palindrome(s,strlen(s))) cout << " not";
cout << " a palindrome\n";
}
}
The strlen(s) call returns the number of characters in the array after the call of read_word(), and cout<<s outputs the characters in the array up to the terminating 0.
We consider this “array solution” significantly messier than the “string solution,” and it gets much worse if we try to seriously deal with the possibility of long strings. See exercise 10.
18.7.3 Palindromes using pointers
Instead of using indices to identify characters, we could use pointers:
bool is_palindrome(const char* first, const char* last)
// first points to the first letter, last to the last letter
{
while (first < last) { // we haven’t reached the middle
if (*first!=*last) return false;
++first; // move forward
––last; // move backward
}
return true;
}
Note that we can actually increment and decrement pointers. Increment makes a pointer point to the next element of an array and decrement makes a pointer point to the previous element. If the array doesn’t have such a next element or previous element, you have a serious uncaught out-of-range error. That’s another problem with pointers.
We call this is_palindrome() like this:
int main()
{
const int max = 128;
for (char s[max]; read_word(cin,s,max); ) {
cout << s << " is";
if (!is_palindrome(&s[0],&s[strlen(s)–1])) cout << " not";
cout << " a palindrome\n";
}
}
Just for fun, we rewrite is_palindrome() like this:
bool is_palindrome(const char* first, const char* last)
// first points to the first letter, last to the last letter
{
if (first<last) {
if (*first!=*last) return false;
return is_palindrome(first+1,last–1);
}
return true;
}
This code becomes obvious when we rephrase the definition of palindrome: a word is a palindrome if the first and the last characters are the same and if the substring you get by removing the first and the last characters is a palindrome.