Exercise 5-11

In text processing it is sometimes useful to know whether a word has any ascenders or descenders. Ascenders are the parts of lowercase letters that extend above the textline; in the English alphabet, the letters, b, d, f, h, k, l, and t have ascenders. Similarly, the descenders are the parts of lowercase letters that descend below the line; In English, the letters g, j, p, q, and y have descenders. Write a program to determine whether a word has any ascenders or descenders. Extend that program to find the longest word in the dictionary that has neither ascenders nor descenders.

Solution

This exercise is somewhat similar to the one we have just completed (Solution to Exercise 5-10), in which the user provides a list of words and the program filter and display the words that satisfy certain conditions.

Solution Strategy

Here is our Solution Strategy:

1. Have a (bool type) function hasAscender to determine whether a given (string) word contains any ascenders (i.e. the letters b, d, f, h, k, l).
2. Have a (bool type) function hasDescender to determine whether a given (string) word contains any Descenders (i.e. the letters g, j, p, q, and y).
3. Use the usual while / cin / push_back method to read in a set of words.
4. If the word contains any ascenders or descenders, append that word to a vector<string> container called interestingWords. Otherwise, append to another vector<string> container called boringWords.
5. Have a function findLongest that is able to scan through a vector<string> container and return the longest (string) word.
6. Print the vector<string> containers interestingWords and boringWords – in response to the challenge: Write a program to determine whether a word has any ascenders or descenders.
7. Print the longest (string) word of the vector<string> container boringWords – in response to the challenge: Extend that program to find the longest word in the dictionary that has neither ascenders nor descenders.

A Side Note

The writing of the functions hasAscender and hasDescender will involve iterating through the letters within the given word, using multiple “hard-coded” if-conditions to determine whether the words container any ascenders / descenders. I do this because I wish to only use the techniques that have learnt so far. In this particular turns out to be okay as there is only a small handful of conditions need to be written. If we are faced with lots more conditions however, the if-condition techniques might not be as efficient (or the code might get too long).

A disclosure I would therefore like to make here is that in Chapter 6 (next chapter), the author would introduce a more compact method to deal with this type of scenario – using the standard library’s find function. Like the previous exercise, it looks like the author is trying to build up some grounds here before introducing us with the more compact methods.

The Project

This section summarise all the C++ source and header files that I use to accomplish this challenge.

Source File List

• main.cpp
• findLongest.cpp
• hasAscender.cpp
• hasDescender.cpp
• vcout.cpp

Header File List

• findLongest.h
• hasAscender.h
• hasDescender.h
• vcout.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <string>  // string
#include <vector>  // vector
#include "hasAscender.h"   // hasAscender
#include "hasDescender.h"   // hasDescender
#include "findLongest.h"   // findLongest
#include "vcout.h"  // vcout

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  string word;
  vector<string> interestingWords;   // Words that contain either ascenders
                                     // or descenders
  vector<string> boringWords;  // Words that contain neither ascenders
                               // nor descenders

  // Populate vector
  while (cin >> word) {
    if (hasAscender(word) || hasDscender(word))
      interestingWords.push_back(word);
    else
      boringWords.push_back(word);
  }

  // Print the interesting words
  cout << "\nInteresting words (i.e. having ascenders or descenders):"
       << endl;
  vcout(interestingWords);

  // Print the boring words
  cout << "\nBoring words (i.e. having neither ascenders nor descenders):"
       << endl;
  vcout(boringWords);

  // Print the longest boring word
  cout << "\nThis is the longest boring word: " << findLongest(boringWords)
       << endl;

  return 0;
}

findLongest.cpp

#include <string>
#include <vector>

using std::string;
using std::vector;

string findLongest(const vector<string>& words)
{
  string longestWord;
  for (vector<string>::const_iterator i = words.begin(); i != words.end(); ++i) {
    if ( i->size() > longestWord.size() )
      longestWord = *i;
  }
  return longestWord;
}

hasAscender.cpp

#include <string>

using std::string;

bool hasAscender(const string& s)
{
  for (string::const_iterator i = s.begin(); i != s.end(); ++i) {
    if (*i == 'b' || *i == 'd' || *i == 'f' || *i == 'h' || *i == 'k' ||
        *i == 'l' )
      return true;
  }
  return false;
}

hasDescender.cpp

#include <string>

using std::string;

bool hasDscender(const string& s)
{
  for (string::const_iterator i = s.begin(); i != s.end(); ++i) {
    if (*i == 'g' || *i == 'j' || *i == 'p' || *i == 'q' || *i == 'y')
      return true;
  }
  return false;
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

using std::cout;
using std::endl;
using std::string;
using std::vector;

int vcout(const vector<string>& v)
{
    for (vector<string>::const_iterator iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

findLongest.h

#ifndef GUARD_FINDLONGEST_H
#define GUARD_FINDLONGEST_H

#include <string>
#include <vector>

std::string findLongest(const std::vector<std::string>&);

#endif // GUARD_FINDLONGEST_H

hasAscender.h

#ifndef GUARD_HASASCENDER_H
#define GUARD_HASASCENDER_H

#include <string>

bool hasAscender(const std::string&);

#endif // GUARD_HASASCENDER_H

hasDescender.h

#ifndef GUARD_HASDESCENDER_H
#define GUARD_HASDESCENDER_H

#include <string>

bool hasDscender(const std::string&);

#endif // GUARD_HASDESCENDER_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

I now run the program, and provide the list of words. As expected the program correctly identified the words containing (and not-containing) either ascenders or descenders. It also resolves the (first observed) longest word that has neither ascenders nor descenders.

the quick brown fox
jumped over the fence
eeeeeee aceimnorsvwxz
nnnn
i love c++
^Z

Interesting words (i.e. having ascenders or descenders):
the
quick
brown
fox
jumped
the
fence
love

Boring words (i.e. having neither ascenders nor descenders):
over
eeeeeee
aceimnorsvwxz
nnnn
i
c++

This is the longest boring word: aceimnorsvwxz

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000

Exercise 5-10

Palindromes are words that are spelled the same right to left as left to right. Write a program to find all the palindromes in a dictionary. Next, find the longest palindrome.

Solution

Just a bit of disclosure before moving on. In chapter 6 (i.e. the next chapter) the author will introduce a more compact technique to auto detect palindromes. In this post however, I shall build up the solution using only the knowledge we have learnt so far (up to chapter 5). I believe the author is trying to build up the grounds before introducing new C++ techniques.

The solution strategy:

1. As usual, have a means to read in words – using the while / cin / push_back method.
2. Have a home-made function isPalindrome that takes in a string and do the “magic” – return (bool type) true if the string is a palindrome.
3. Have a home-made function lowcase to convert all the letters of a word to lower case. This is to aid the letter comparison process within the isPalindrome function.
4. Have a home-made findLongest function to determine the longest (string) palindrome,
5. Re-use the home-made vcout function to display the string elements witin a vector<string> container. e.g. the vector containing the palindromes.

The isPalindrome Algorithm

A palindrome is a word that read the same in both directions. This function essentially require two iterators a and b, in which iterator a start from the first to last letter of the word, whereas iterator b (is vice versa, ) start from the last to the first of the word. The function compare the two underlying letters regardless of case. (To do this I have a home-made lowcase function that will convert all the letters to lower case first prior the comparing – the lowcase function is very simple, rather than explaining in-depth here, just look at the code lowcase.cpp under the Project section.). The following diagram summarise the isPalindrome function logic.

See the Project section for the full code for isPalindrome.

The Project

Wrapping up all the source and header files here all in one place.

Source File List

• main.cpp
• findLongest.cpp
• isPalindrome.cpp
• lowcase.cpp
• vcout.cpp

Header File List

• findLongest.h
• isPalindrome.h
• lowcase.h
• vcout.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <string>
#include <vector>
#include "vcout.h"  // vcout
#include "isPalindrome.h"   // isPalindrome
#include "findLongest.h"   // findLongest

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  string word;
  vector<string> words;
  vector<string> palindromes;

  // Populate vector
  while (cin >> word) {
    if (isPalindrome(word))
      palindromes.push_back(word);
  }

  // Print palindrome
  cout << "\nThese are the palindromes identified: " << endl;
  vcout(palindromes);

  // Print longest palindrome (take first observed)
  cout << "\nThe (first observed) longest palindrome is:\n"
       << findLongest(palindromes) << endl;

  return 0;
}

findLongest.cpp

#include <string>
#include <vector>

using std::string;
using std::vector;

string findLongest(const vector<string>& words)
{
  string longestWord;
  for (vector<string>::const_iterator i = words.begin(); i != words.end(); ++i) {
    if ( i->size() > longestWord.size() )
      longestWord = *i;
  }
  return longestWord;
}

isPalindrome.cpp

#include <string>
#include "lowcase.h"

using std::string;

bool isPalindrome(const string& s)
{

  string word = lowcase(s);

  string::const_iterator a = word.begin();
  string::const_iterator b = word.end() - 1;

  while ( a <= b && a != word.end()) {
    if ( *a != *b )
      return false;
    ++a;
    --b;
  }
  return true;
}

lowcase.cpp

#include <string>
#include <cctype>

using std::string;
using std::tolower;

string lowcase(const string& s)
{
    string ret;
    for (string::size_type i = 0; i != s.size(); ++i)
    {
        ret.push_back(tolower(s[i]));
    }
    return ret;
}

vcout.cpp

#include <iostream>
#include <string>    // string
#include <vector>    // vector

using std::cout;
using std::endl;
using std::string;
using std::vector;

int vcout(const vector<string>& v)
{
    for (vector<string>::const_iterator iter = v.begin();
         iter != v.end(); ++iter)
    {
        cout << (*iter) << endl;
    }
    return 0;
}

Header Files

findLongest.h

#ifndef GUARD_FINDLONGEST_H
#define GUARD_FINDLONGEST_H

#include <string>
#include <vector>

std::string findLongest(const std::vector<std::string>&);

#endif // GUARD_FINDLONGEST_H

isPalindrome.h

#ifndef GUARD_ISPALINDROME_H
#define GUARD_ISPALINDROME_H

#include <string>

bool isPalindrome(const std::string&);

#endif // GUARD_ISPALINDROME_H

lowcase.h

#ifndef GUARD_LOWCASE_H
#define GUARD_LOWCASE_H

#include <string>

std::string lowcase(const std::string&);

#endif // GUARD_LOWCASE_H

vcout.h

#ifndef GUARD_VCOUT_H
#define GUARD_VCOUT_H

#include <string>
#include <vector>

int vcout(const std::vector<std::string>&);

#endif // GUARD_VCOUT_H

Test Program

The program allows us to enter a list of words, and automatically display the palindromes (if any), followed by the longest palindrome.

bib good Morning bob dad Abba
Hello Deed Civic Solos
Redder Kelly DEIfied rOtaToR
^Z

These are the palindromes identified:
bib
bob
dad
Abba
Deed
Civic
Solos
Redder
DEIfied
rOtaToR

The (first observed) longest palindrome is:
DEIfied

As expected, the determination of palindromes is regardless of upper / lower case letters.

Further Readings

Purely out of curosity, palindrome applies not only to words, but also to phrases. For instance, the following phrases read the same in both direction.

(Reference: http://www.highlightpress.com.au/list-of-palindromes.html)

• Able I was ere I saw Elba
• Ah, Satan sees Natasha
• A man, a plan, a canal: Panama
• Do geese see God?
• Live not on evil
• Murder for a jar of red rum
• Never odd or even
• No, it is opposition

What about, to write a C++ program to determine palindrome sentences? That would be interesting.

I guess the algorithm would be just a matter of:

1. Using the standard C++ getline function to read and parse in the whole sentences instead of just words.
2. Removing all the special characters such as punctuations and empty spaces within the sentences.
3. Converting all letters to lower cases.
4. Applying the isPalindrome function against the newly formatted sentences. (i.e. treat the formatted sentences as “words”)

Something for later maybe!

Reference

Koenig, Andrew & Moo, Barbara E., Accelerated C++, Addison-Wesley, 2000