This is Part 6 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 6 / 7)

Relating to section 6.3.1 of the textbook (page 117-118). Implement and test out the “two-pass extract_fails” program. This program essentially split the students into two groups – failed and passed students. This version of extract_fails function uses remove_copy_if and erase from the <algorithm> directive. (Note that the original version of extract_fails function was first introduced in Chapter 5 / my Solution to Exercise 5-0.)

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• extract_fails.cpp
• fgrade.cpp
• grade.cpp
• median.cpp
• pgrade.cpp
• Student_info.cpp

Header File List

• extract_fails.h
• fgrade.h
• grade.h
• median.h
• pgrade.h
• Student_info.h

Source Files

main.cpp

#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <vector>            // std::vector
#include <algorithm>         // std::sort
#include "Student_info.h"    // Student_info, read
#include "extract_fails.h"   // extract_fails
#include "grade.h"  // grade

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

int main()
{
    vector<Student_info> students;
    Student_info record;

    // read and store all the student's data.
    while (read(cin, record))
        students.push_back(record);

    // Extract the failed students
    vector<Student_info> students_failed = extract_fails(students);

    // sort vectors
    sort(students.begin(),students.end(),compare);
    sort(students_failed.begin(),students_failed.end(),compare);

    // Report passing students
    cout << "These students have passed." << endl;
    for (vector<Student_info>::const_iterator i = students.begin();
         i != students.end(); ++i)
        cout << i->name << " (" << grade(*i) << ")" << endl;

    // Report failing students
    cout << "These students have failed." << endl;
    for (vector<Student_info>::const_iterator i = students_failed.begin();
         i != students_failed.end(); ++i)
        cout << i->name << " (" << grade(*i) << ")" << endl;

    return 0;
}

extract_fails.cpp

#include <vector>             // std::vector
#include <algorithm>          // std::remove_copy_if

#include "Student_info.h"
#include "fgrade.h"
#include "pgrade.h"

using std::vector;

// A two-pass solution to extract the failed students
// (S6.3.1/117)
vector<Student_info> extract_fails(vector<Student_info>& students)
{
  vector<Student_info> fail;
  remove_copy_if(students.begin(), students.end(),
                 back_inserter(fail), pgrade);
  students.erase(remove_if(students.begin(), students.end(), fgrade),
                 students.end() );
  return fail;
}

fgrade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"         // grade

// predicate to determine whether a student failed
// (S5.1/75)
bool fgrade(const Student_info& s)
{
    return grade(s) < 60;
}

grade.cpp

#include <stdexcept>
#include <vector>
#include "grade.h"
#include "median.h"
#include "Student_info.h"

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
// (S4.1.1/53)
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

pgrade.cpp

#include "Student_info.h"  // Student_info
#include "fgrade.h"        // fgrade

// predicate to determine whether a student has passed (not failed)
// (S6.3.1/117)
bool pgrade(const Student_info& s)
{
    return !fgrade(s);
}

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

Header Files

extract_fails.h

#ifndef GUARD_EXTRACT_FAILS_H
#define GUARD_EXTRACT_FAILS_H

// extract_fails.h

#include <vector>
#include "Student_info.h"

std::vector<Student_info> extract_fails(std::vector<Student_info>&);

#endif // GUARD_EXTRACT_FAILS_H

fgrade.h

#ifndef GUARD_FGRADE_H
#define GUARD_FGRADE_H

// fgrade.h

#include "Student_info.h"  // Student_info
#include "grade.h"         // grade

bool fgrade(const Student_info&);

#endif // GUARD_FGRADE_H

grade.h

#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

// grade.h

#include <vector>
#include "Student_info.h"

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

#endif // GUARD_GRADE_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

// median.h

#include <vector>

double median(std::vector<double>);

#endif // GUARD_MEDIAN_H

pgrade.h

#ifndef GUARD_PGRADE_H
#define GUARD_PGRADE_H

// pgrade.h

#include "Student_info.h"  // Student_info

bool pgrade(const Student_info&);

#endif // GUARD_PGRADE_H

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h

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

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

Test Program

I now provide a set of student grades. The program separate the students to the pass and fail groups as expected.

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z
These students have passed.
bob (60)
ken (65.6)
pete (100)
These students have failed.
anna (24)
bill (39.2)
gary (48)
jay (51.4)
jon (54)
mary (50)

Reference

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

This is Part 5 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 5 / 7)

Relating to section 6.2 of the textbook (page 110-116). Implement and test out the “Comparing Grading Schemes” program. This program reads in a set of student’s grades (from mid-term exam, final exam, and individual homework grades), compute the student’s final grades using the 3 grading schemes (median homework, average homework, and optimistic-median homework), split the students into two groups (did and didn’t do all homework), and for each group compute the group medians associating with the grading schemes. i.e. the end result consists of 6 total grades: medians computed using the 3 schemes for group A (students who did all homework), and medians computed using the 3 schemes for group B (students who didn’t do all homework). The exercise introduces one key idea: parsing a function as an argument to another function. From Chapter 10 we shall see this is actually facilitated by the “hidden” pointer and array mechanism.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• average.cpp
• average_analysis.cpp
• average_grade.cpp
• did_all_hw.cpp
• grade.cpp
• grade_aux.cpp
• median.cpp
• median_analysis.cpp
• optimistic_median.cpp
• optimistic_median_analysis.cpp
• Student_info.cpp
• write_analysis.cpp

Header File List

• average.h
• average_analysis.h
• average_grade.h
• did_all_hw.h
• grade.h
• grade_aux.h
• median.h
• median_analysis.h
• optimistic_median.h
• optimistic_median_analysis.h
• Student_info.h
• write_analysis.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <vector>  // vector

#include "Student_info.h"  // Student_info
#include "did_all_hw.h"  // did_all_hw
#include "write_analysis.h"  // write_analysis

#include "median_analysis.h"  // median_analysis
#include "average_analysis.h"  // average_analysis
#include "optimistic_median_analysis.h"  // optimistic_median_analysis

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

// Compare the Grading Scheme
// (S6.2.3/114)
int main()
{
  // students who did and didn't do all their homework
  vector<Student_info> did, didnt;

  // read the student records and partition them
  Student_info student;
  while (read(cin, student)) {
    if (did_all_hw(student))
      did.push_back(student);
    else
      didnt.push_back(student);
  }

  // verify that the analyses will show us something
  if (did.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }
  if (didnt.empty()) {
    cout << "No student did all the homework!" << endl;
    return 1;
  }

  // do the analyses
  write_analysis(cout, "median", median_analysis, did, didnt);
  write_analysis(cout, "average", average_analysis, did, didnt);
  write_analysis(cout, "median of homework turned in",
                 optimistic_median_analysis, did, didnt);

  return 0;
}

average.cpp

#include <vector>  // vector
#include <numeric>  // numeric

using std::vector;
using std::accumulate;

// Compute average of elements
// (S6.2.3/115)
double average(const vector<double>& v)
{
  return accumulate(v.begin(), v.end(), 0.0) / v.size();
}

average_analysis.cpp

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "average_grade.h"  // average_grade
#include "median.h"  // median

using std::vector;
using std::transform;

// Perform average analysis
// (S6.2.3/115)
double average_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), average_grade);
  return median(grades);
}

average_grade.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "average.h"  // average

// Compute the final grade using average of homework
// (S6.2.3/115)
double average_grade(const Student_info& s)
{
  return grade(s.midterm, s.final, average(s.homework));
}

did_all_hw.cpp

#include <algorithm>  // find
#include "Student_info.h"  // Student_info

// Has the student done all the homework?
// (S6.2.1/110)
bool did_all_hw(const Student_info& s)
{
  return ((find(s.homework.begin(), s.homework.end(), 0)) == s.homework.end());
}

grade.cpp

#include <stdexcept>
#include <vector>
#include "grade.h"
#include "median.h"
#include "Student_info.h"

using std::domain_error;
using std::vector;

// definitions for the grade functions from S4.1/52, S4.1.2/54, S4.2.2/63

// compute a student's overall grade from midterm and final exam
// grades and homework grade (S4.1/52)
double grade(double midterm, double final, double homework)
{
    return 0.2 * midterm + 0.4 * final + 0.4 * homework;
}

// compute a student's overall grade from midterm and final exam grades
// and vector of homework grades.
// this function does not copy its argument, because median (function) does it for us.
// (S4.1.2/54)
double grade(double midterm, double final, const vector<double>& hw)
{
    if (hw.size() == 0)
        throw domain_error("student has done no homework");
    return grade(midterm, final, median(hw));
}

// this function computes the final grade for a Student_info object
// (S4.2.2/63)
double grade(const Student_info& s)
{
    return grade(s.midterm, s.final, s.homework);
}

grade_aux.cpp

#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include <stdexcept>  // domain_error

using std::domain_error;

// Auxiliary function to be parsed as argument to a function
// (S6.2.2/113)
double grade_aux(const Student_info& s)
{
  try {
    return grade(s);
  } catch (domain_error) {
    return grade(s.midterm, s.final, 0);
  }
}

median.cpp

// source file for the median function
#include <algorithm>
#include <stdexcept>
#include <vector>

using std::domain_error;
using std::sort;
using std::vector;

// compute the median of a vector<double>
double median(vector<double> vec)
{
    typedef vector<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if (size == 0)
        throw domain_error("median of an empty vector");

    sort(vec.begin(),vec.end());

    vec_sz mid = size/2;

    return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

median_analysis.cpp

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "grade_aux.h"  // grade
#include "median.h"  // median

using std::vector;
using std::transform;

// S6.2.2/112
double median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(), back_inserter(grades), grade_aux);
  return median(grades);
}

optimistic_median.cpp

#include <vector>  // vector
#include <algorithm>  // remove_copy, back_inserter
#include "Student_info.h"  // Student_info
#include "grade.h"  // grade
#include "median.h"  // median

using std::vector;

// median of the nonzero elements of s.homework, or 0 if no such elements exist
double optimistic_median(const Student_info& s)
{
  vector<double> nonzero;
  remove_copy(s.homework.begin(), s.homework.end(),
              back_inserter(nonzero), 0);
  if (nonzero.empty())
    return grade(s.midterm, s.final, 0);
  else
    return grade(s.midterm, s.final, median(nonzero));
}

optimistic_median_analysis.cpp

#include <vector>  // vector
#include <algorithm>  // transform
#include "Student_info.h"  // Student_info
#include "optimistic_median.h" // optimistic_median
#include "median.h"  // median

using std::vector;
using std::transform;

// Auxiliary function
// (S6.2.3/115) - adjust accordingly
double optimistic_median_analysis(const vector<Student_info>& students)
{
  vector<double> grades;
  transform(students.begin(), students.end(),
            back_inserter(grades), optimistic_median);
  return median(grades);
}

Student_info.cpp

#include "Student_info.h"

using std::istream;
using std::vector;

// we are interested in sorting the Student_info object by the student's name
bool compare(const Student_info& x, const Student_info& y)
{
    return x.name < y.name;
}

// read student's name, midterm exam grade, final exam grade, and homework grades
// and store into the Student_info object
// (as defined in S4.2.2/62)
istream& read(istream& is, Student_info& s)
{
    // read and store the student's name and midterm and final exam grades
    is >> s.name >> s.midterm >> s.final;

    // read and store all the student's homework grades
    read_hw(is, s.homework);
    return is;
}

// read homework grades from an input stream into a vector<double>
// (as defined in S4.1.3/57)
istream& read_hw(istream& in, vector<double>& hw)
{
    if (in)
    {
        // get rid of previous contents
        hw.clear();

        // read homework grades
        double x;
        while (in >> x)
            hw.push_back(x);

        // clear the stream so that input will work for the next student
        in.clear();
    }
    return in;
}

write_analysis.cpp

#include <iostream>  // ostream, endl;
#include <vector>  // vector
#include <string>  // string
#include "Student_info.h"  // Student_info

using std::ostream;
using std::endl;
using std::string;
using std::vector;

// Output result to compare the two groups of students who did and
// who didn't do all of their homework.
// (S6.2.3/113)
void write_analysis(ostream& out,
                    const string& name,
                    double analysis(const vector<Student_info>&),
                    const vector<Student_info>& did,
                    const vector<Student_info>& didnt)
{
  out << name << ": median(did) = " << analysis(did) <<
                 ": median(didnt) = " << analysis(didnt) << endl;
  return;
}

Header Files

average.h

#ifndef GUARD_AVERAGE_H
#define GUARD_AVERAGE_H

// average.h
#include <vector>

double average(const std::vector<double>&);

#endif // GUARD_AVERAGE_H

average_analysis.h

#ifndef GUARD_AVERAGE_ANALYSIS_H
#define GUARD_AVERAGE_ANALYSIS_H

// average_analysis.h

#include <vector>

double average_analysis(const std::vector<Student_info>&);

#endif // GUARD_AVERAGE_ANALYSIS_H

average_grade.h

#ifndef GUARD_AVERAGE_GRADE_H
#define GUARD_AVERAGE_GRADE_H

// average_grade.h
#include "Student_info.h"  // Student_info

double average_grade(const Student_info&);

#endif // GUARD_AVERAGE_GRADE_H

did_all_hw.h

#ifndef GUARD_DID_ALL_HW_H
#define GUARD_DID_ALL_HW_H

// did_all_hw.h
#include "Student_info.h"  // Student_info

bool did_all_hw(const Student_info&);

#endif // GUARD_DID_ALL_HW_H

grade.h

#ifndef GUARD_GRADE_H
#define GUARD_GRADE_H

// grade.h
#include <vector>
#include "Student_info.h"

double grade(double, double, double);
double grade(double, double, const std::vector<double>&);
double grade(const Student_info&);

#endif // GUARD_GRADE_H

grade_aux.h

#ifndef GUARD_GRADE_AUX_H
#define GUARD_GRADE_AUX_H

// grade_aux.h
#include "Student_info.h"  // Student_info

double grade_aux(const Student_info&);

#endif // GUARD_GRADE_AUX_H

median.h

#ifndef GUARD_MEDIAN_H
#define GUARD_MEDIAN_H

// median.h
#include <vector>
double median(std::vector<double>);

#endif // GUARD_MEDIAN_H

median_analysis.h

#ifndef GUARD_MEDIAN_ANALYSIS_H
#define GUARD_MEDIAN_ANALYSIS_H

// median_analysis.h
#include <vector>
#include "Student_info.h"  // Student_info

double median_analysis(const std::vector<Student_info>&);

#endif // GUARD_MEDIAN_ANALYSIS_H

optimistic_median.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_H
#define GUARD_OPTIMISTIC_MEDIAN_H

// optimistic_median.h

#include "Student_info.h"  // Student_info

double optimistic_median(const Student_info&);

#endif // GUARD_OPTIMISTIC_MEDIAN_H

optimistic_median_analysis.h

#ifndef GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_H
#define GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_H

// optimistic_median_analysis.h

#include <vector>

double optimistic_median_analysis(const std::vector<Student_info>&);

#endif // GUARD_OPTIMISTIC_MEDIAN_ANALYSIS_H

Student_info.h

#ifndef GUARD_STUDENT_INFO_H
#define GUARD_STUDENT_INFO_H

// Student_info.h
#include <iostream>
#include <string>
#include <vector>

struct Student_info
{
    std::string name;
    double midterm, final;
    std::vector<double> homework;
};

bool compare(const Student_info&, const Student_info&);
std::istream& read(std::istream&, Student_info&);
std::istream& read_hw(std::istream&, std::vector<double>&);

#endif // GUARD_STUDENT_INFO_H

write_analysis.h

#ifndef GUARD_WRITE_ANALYSIS_H
#define GUARD_WRITE_ANALYSIS_H

// write_analysis.h

#include <iostream>  // ostream;
#include <vector>  // vector
#include <string>  // string
#include "Student_info.h"  // Student_info

void write_analysis(std::ostream&,
                    const std::string&,
                    double analysis(const std::vector<Student_info>&),
                    const std::vector<Student_info>&,
                    const std::vector<Student_info>&);

#endif // GUARD_WRITE_ANALYSIS_H

Test Program

I now submit a set of hypyethetical student grades. As expected, the optimistic scheme (3rd one), gives higher median grades for the students who didn’t do all the homework.

pete 100 100 100 100 100
jon 90 90 0 0 0
mary 50 50 50 50 50
anna 40 40 0 0 0
gary 80 80 0 80 0
bob 100 100 100 0 0
ken 20 88 99 44 66
jay 99 39 40 80 0
bill 20 88 0 39 0
^Z
^Z
median: median(did) = 65.6: median(didnt) = 49.7
average: median(did) = 67.0667: median(didnt) = 52.7
median of homework turned in: median(did) = 65.6: median(didnt) = 57.1

Reference

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

This is Part 4 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 4 / 7)

Relating to section 6.1.3 of the textbook (page 105-109). Implement and test out the “Finding URLs” program. The program scans a line of input text, and automatically detect and display all the URL addresses within that line of text.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• find_urls.cpp
• not_url_char.cpp
• url_beg.cpp
• url_end.cpp
• vcout.cpp

Header File List

• find_urls.h
• not_url_char.h
• url_beg.h
• url_end.h
• vcout.h

Source Files

main.cpp

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

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

int main()
{
    cout << "Enter a line. This program automatically find URLs..." << endl;

    // Read a line of input, then find and display URLs.
    string line;
    vector<string> urls;
    while (getline(cin, line)) {
      vector<string> urls = find_urls(line);
      vcout(urls);
    }

    return 0;
}

find_urls.cpp

#include <string>  // string
#include <vector>  // vector
#include "url_beg.h"  // url_beg
#include "url_end.h"  // url_end

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

vector<string> find_urls(const string& s)
{
  vector<string> ret;
  typedef string::const_iterator iter;
  iter b = s.begin(), e = s.end();

  // look through the entire input
  while (b != e) {

    // look for one or more letters followed by ://
    b = url_beg(b, e);

    // if we found it
    if (b != e) {
      // get the rest of the URL
      iter after = url_end(b, e);

      // remember the URL
      ret.push_back(string(b, after));

      // advance b and check for more URLs on this line
      b = after;
    }
  }
  return ret;
}

not_url_char.cpp

<br />#include <string>          // string, isalnum
#include <algorithm>       // find

using std::string;

bool not_url_char(char c)
{
  // characters, in addition to alphanumerics, that can appear in a URL
  static const string url_ch = "~;/?:@=&$-_.+!*'(),";

  // see whether c can appear in a URL and return the negative
  return !(isalnum(c) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end() );
}

url_beg.cpp

#include <string>  // string, isalpha
#include <algorithm>  // search
#include "not_url_char.h"  // not_url_char

using std::string;

string::const_iterator
url_beg(string::const_iterator b, string::const_iterator e)
{
  static const string sep = "://";
  typedef string::const_iterator iter;

  // i marks where the separator was found
  iter i = b;

  while ((i = search(i, e, sep.begin(), sep.end() )) != e) {

    // make sure the separator isn't at the beginning or end of the line
    if (i != b && i + sep.size() != e) {

      // beg marks the beginning of the protocol-name
      iter beg = i;
      while (beg != b && isalpha(beg[-1]))
        --beg;

      // is there at least one appropriate character before and after the separator?
      if (beg != i && !not_url_char(i[sep.size()]))
        return beg;
    }

    // the separator we found wasn't part of a URL; advance i past this separator
    i += sep.size();
  }
  return e;
}

url_end.cpp

#include <string>  // string
#include <vector>  // vector
#include <algorithm>  // find_if
#include "not_url_char.h"  // not_url_char

using std::string;

string::const_iterator
url_end(string::const_iterator b, string::const_iterator e)
{
  return find_if(b, e, not_url_char);
}

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 i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Header Files

find_urls.h

#ifndef GUARD_FIND_URLS_H
#define GUARD_FIND_URLS_H

#include <vector>
#include <string>

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

#endif // GUARD_FIND_URLS_H

not_url_char.h

#ifndef GUARD_NOT_URL_CHAR_H
#define GUARD_NOT_URL_CHAR_H

bool not_url_char(char);

#endif // GUARD_NOT_URL_CHAR_H

url_beg.h

#ifndef GUARD_URL_BEG_H
#define GUARD_URL_BEG_H

std::string::const_iterator
url_beg(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_BEG_H

url_end.h

#ifndef GUARD_URL_END_H
#define GUARD_URL_END_H

#include <string>

std::string::const_iterator
url_end(std::string::const_iterator, std::string::const_iterator);

#endif // GUARD_URL_END_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

Let’s do some simple tests:

• Submitting the line “Have you tried http://google.co.uk and http://bbc.co.uk ?”, the program should return: “http://google.co.uk” and “http://bbc.co.uk”.
• Submitting the line “Have you tried http:// or google.co.uk or http://google.co.uk ?”, the program should return: “http://google.co.uk”.
• Submitting the line “Have you tried http or :// or http://bbc.co.uk ?”, the program should return: “http://bbc.co.uk “.

Reference

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

This is Part 3 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 3 / 7)

Relating to section 6.1.2 of the textbook (page 105). Implement and test out the home-made isPalindrome function (created using the equal utility). Note that this is a more neat / compact version to the created in my previous Solution to Exercise 5-10.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• isPalindrome.cpp
• vcout.cpp

Header File List

• isPalindrome.h
• vcout.h

Source Files

main.cpp

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

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);

  return 0;
}

isPalindrome.cpp

#include <string>

using std::string;

bool isPalindrome(const string& s)
{
  return equal(s.begin(), s.end(), s.rbegin() );
}

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 i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Header Files

isPalindrome.h

#ifndef GUARD_ISPALINDROME_H
#define GUARD_ISPALINDROME_H

#include <string>

bool isPalindrome(const std::string&);

#endif // GUARD_ISPALINDROME_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 know enter a list of words. The program should automatically identify and display the palindrome. Note that for simplicity sake the program is case sensitive – in this test I shall strictly stick to lower case letters. I shall type in the following lines:

• good morning bob
• lol what a beautiful moon
• eeeeeeeee aaaaaaa banana

The the program should identify these words as palindromes (as they spell the same in both directions): bob, lol, a, eeeeeeeee, aaaaaaa

good morning bob
lol what a beautiful moon
eeeeeeeee aaaaaaa banana
^Z

These are the palindromes identified:
bob
lol
a
eeeeeeeee
aaaaaaa

Reference

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

This is Part 2 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 2 / 7)

Relating to section 6.1.1 of the textbook (page 103-105). Implement and test out an alternative way to split a line into words using the find_if utility from the <algorithm> directive. The original split function method was first introduced in S5.6/88 of the book.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• split.cpp
• vcout.cpp

Header File List

• split.h
• vcout.h

Source Files

main.cpp

</p>

<h1>include &lt;iostream&gt;</h1>

<h1>include &lt;string&gt;</h1>

<h1>include &lt;vector&gt;</h1>

<h1>include &quot;vcout.h&quot;</h1>

<h1>include &quot;split.h&quot;</h1>

<p>using std::string;
using std::vector;
using std::cin;
using std::cout;
using std::endl;</p>

<p>int main()
{
    // Read a line of input, split into words, and display
    string line;
    vector&lt;string&gt; words;
    while (getline(cin, line)) {
      vector&lt;string&gt; words = split(line);
      vcout(words);
    }</p>

<pre><code>return 0;
</code></pre>

<p>}</p>

<p>

split.cpp

</p>

<h1>include &lt;string&gt;    // string</h1>

<h1>include &lt;vector&gt;    // vector</h1>

<h1>include &lt;cctype&gt;    // isspace</h1>

<h1>include &lt;algorithm&gt;  // find_if</h1>

<p>using std::vector;
using std::string;
using std::isspace;
using std::find_if;</p>

<p>// true if the argument is whitespace, false otherwise
// (S6.1.1/103)
bool space(char c)
{
  return isspace(c);
}</p>

<p>// false if the argument is whitespace, true otherwise
// (S6.1.1/103)
bool not_space(char c)
{
  return !isspace(c);
}</p>

<p>// Scan a line and split into words. Return a vector that contains these words.
// (S6.1.1/103)
vector&lt;string&gt; split(const string&amp; str)
{
  typedef string::const_iterator iter;
  vector&lt;string&gt; ret;</p>

<p>iter i = str.begin();
  while (i != str.end()) {</p>

<pre><code>// Ignore leading blanks
i = find_if(i, str.end(), not_space);

// Find end of next word
iter j = find_if(i, str.end(), space);

// Copy the characters in ([i, j)
if (i != str.end())
  ret.push_back(string(i, j));

// Re-initialize
i = j;
</code></pre>

<p>}
  return ret;
}</p>

<p>

vcout.cpp

</p>

<h1>include &lt;iostream&gt;</h1>

<h1>include &lt;string&gt;    // string</h1>

<h1>include &lt;vector&gt;    // vector</h1>

<p>using std::cout;
using std::endl;
using std::string;
using std::vector;</p>

<p>int vcout(const vector&lt;string&gt;&amp; v)
{
  for (vector&lt;string&gt;::const_iterator i = v.begin(); i != v.end(); ++i)
    cout &lt;&lt; (*i) &lt;&lt; endl;</p>

<p>return 0;
}</p>

<p>

Header Files

split.h

</p>

<h1>ifndef GUARD_SPLIT_H</h1>

<h1>define GUARD_SPLIT_H</h1>

<h1>include &lt;vector&gt;</h1>

<h1>include &lt;string&gt;</h1>

<p>std::vector&lt;std::string&gt; split(const std::string&amp;);</p>

<h1>endif // GUARD_SPLIT_H</h1>

<p>

vcout.h

</p>

<h1>ifndef GUARD_VCOUT_H</h1>

<h1>define GUARD_VCOUT_H</h1>

<h1>include &lt;string&gt;</h1>

<h1>include &lt;vector&gt;</h1>

<p>int vcout(const std::vector&lt;std::string&gt;&amp;);</p>

<h1>endif // GUARD_VCOUT_H</h1>

<p>

Test Program

By entering a text line, say, “The quick brown fox jumped over the fence”, the program should be able to dice in into words and display accordingly.

The quick brown fox jumped over the fence
The
quick
brown
fox
jumped
over
the
fence
^Z

Reference

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

This is Part 1 of the 7-part Exercise 6-0. Click here to see the other parts.

Exercise 6-0 (Part 1 / 7)

Relating to section 6.1 of the textbook (page 101-103). There are many ways to append elements from container B to container A (the base). In this post I shall implement and test out 3 known ways to do this: (1) pusb_back method, (2) insert method, and (3) copy method. The test confirms that all 3 methods produce the same results.

The Project

This section summarises the partitioned program in the form of C++ source and header files.

Source File List

• main.cpp
• vcout.cpp

Header File List

• vcout.h

Source Files

main.cpp

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

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

int main()
{
  string word;               // a word

  vector<string> wordCollectionA;    // a collection of words
  cout << "Define vector<string> wordCollectionA below..." << endl;
  // Populate wordCollectionA.
  while (cin >> word)
    wordCollectionA.push_back(word);
  cin.clear();

  vector<string> wordCollectionB;    // another collection of words
  cout << "Define vector<string> wordCollectionB below..." << endl;
  // Populate wordCollectionB.
  while (cin >> word)
    wordCollectionB.push_back(word);
  cin.clear();

  // Test appending using the push_back method
  vector<string> baseForPushBack = wordCollectionA;
  for (vector<string>::const_iterator i = wordCollectionB.begin();
       i != wordCollectionB.end(); ++i)
    baseForPushBack.push_back(*i);

  // Test appending using the insert method
  vector<string> baseForInsert = wordCollectionA;
  baseForInsert.insert(baseForInsert.end(), wordCollectionB.begin(), wordCollectionB.end());

  // Test appending using the copy method
  vector<string> baseForCopy = wordCollectionA;
  copy(wordCollectionB.begin(), wordCollectionB.end(),
       back_inserter(baseForCopy) );

  // Display results
  cout << "Append wordCollectionB to wordCollectionA with push_back method..."
      << endl;
  vcout(baseForPushBack);
  cout << "Append wordCollectionB to wordCollectionA with insert method..."
      << endl;
  vcout(baseForInsert);
  cout << "Append wordCollectionB to wordCollectionA with copy method..."
      << endl;
  vcout(baseForCopy);

  return 0;
}

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 i = v.begin(); i != v.end(); ++i)
    cout << (*i) << endl;

  return 0;
}

Header Files

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

Result

The test demonstrates that all 3 methods are equivalent – they produce the same result and serve the same purpose. i.e. appending elements to the base container.

Imagine:

• We have a vector<string> wordCollectionA container that contains the string elements “Item0” and “Item1”.
• We have a vector<string> wordCollectionB container that contains the string elements “Item2”, “Item3” and “Item4”.
• Appending the elements in wordCollectionB to the (base) wordCollectionA should result in A containing “Item0”, “Item1”, “Item2”, “Item3” and “Item4”.

Define vector<string> wordCollectionA below...
Item0
Item1
^Z
Define vector<string> wordCollectionB below...
Item2
Item3
Item4
^Z
Append wordCollectionB to wordCollectionA with push_back method...
Item0
Item1
Item2
Item3
Item4
Append wordCollectionB to wordCollectionA with insert method...
Item0
Item1
Item2
Item3
Item4
Append wordCollectionB to wordCollectionA with copy method...
Item0
Item1
Item2
Item3
Item4

Reference

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

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

Exercise 5-9

Write a program to write the words in the input that do not contain any uppercase letters followed by words that contain one or more uppercase letters.

Solution

To clarify, the objective of this exercise is to:

• read in a list of words
• print the words that are all pure lower case.
• print the words that contain at least one upper case letter.

To do this, we will need to:

1. Use the usual while/cin/push_back method to read in a list of words.
2. Create a function hasUpcaseLetters to determine whether a word contains any upper case letters at all.
3. If word contains no upper case letters, append to vector<string> allLowcaseLetterWords.
4. Otherwise if word contains at least one upper case letters, append to vector<string> someUpcaseLetterWords.
5. (Optional) re-use the home-made function vcout to print the two word lists to the console output.

The Project

These are the files that I use. The main program should sum up the logic job flow.

 

Source File List

• main.cpp
• hasUpcaseLetters.cpp
• vcout.cpp

Header File List

• hasUpcaseLetters.h
• vcout.h

Source Files

main.cpp

#include <iostream>  // cin, cout, endl
#include <string>
#include <vector>
#include "hasUpcaseLetters.h"  // hasUpcaseLetters
#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> allLowcaseLetterWords;
    vector<string> someUpcaseLetterWords;

    // Populate vectors
    while (cin >> word) {
        if (hasUpcaseLetters(word))
            someUpcaseLetterWords.push_back(word);
        else
            allLowcaseLetterWords.push_back(word);
    }

    // Print words with at least 1 upper case letter
    cout << "\nThese words contain at least one upper case letter: " << endl;
    vcout(someUpcaseLetterWords);

    // Print pure lower case words
    cout << "\nThese words are pure lower case letters: " << endl;
    vcout(allLowcaseLetterWords);

    return 0;
}

hasUpcaseLetters.cpp

#include <cctype>  // isupper
#include <string>  // string

using std::isupper;
using std::string;

bool hasUpcaseLetters(const string& aWord)
{
    for (string::const_iterator i = aWord.begin(); i != aWord.end(); ++i) {
        if (isupper(*i))
            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

hasUpcaseLetters.h

#ifndef GUARD_HASUPCASELETTERS_H
#define GUARD_HASUPCASELETTERS_H

#include <string>

bool hasUpcaseLetters(const std::string&);

#endif // GUARD_HASUPCASELETTERS_H

vcout.h

#ifndef GUARD_HASUPCASELETTERS_H
#define GUARD_HASUPCASELETTERS_H

#include <string>

bool hasUpcaseLetters(const std::string&);

#endif // GUARD_HASUPCASELETTERS_H

Test Result

A simple test shows the program works as expected.

Apple
apple
APPLE
aPpLe
applE
orange
oRange
ORANGE
orangE
^Z

These words are pure lower case letters:
apple
orange

These words contain at least one upper case letter:
Apple
APPLE
aPpLe
applE
oRange
ORANGE
orangE

Reference

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

Exercise 5-8

In the hcat function from S5.8.3/95, what would happen if we defined s outside the scope of the while? Rewrite and execute the program to confirm your hypothesis.

Solution

Note: the original hcat function may be found in my Solution to Exercise 5-0 (Part 3/3). The objective of this exercise is to understand what may happen should we vary the hcat function a little bit.

In short, defining the string s outside the while loop will cause problems for certain horizontal concatenation scenarios (this will explained shortly below). It is however ok to define that string s outside the while loop, as long as we also add a one-line statement inside the while loop (this will also be explained shortly below).

Potential Problem

This is what the hcat function looks like if we simply move the string s outside (or just before) the while loop.

Assuming we wish to use the hcat function to concatenate the following (left and right) vectors:

When the hcat function is invoked, the following tables summarise what happens:

Note that at the beginning of the second loop, because we did not re-initialise the string s, it causes the the s.size() to become larger than width1 (which is the maximum length of the longest string element within the left vector). This effectively results in negative string length when we apply the s += string(width1 – s.size(), ‘ ‘). The C++ implementation will likely bump into a string length error – highlighted in red.

Below shows what happens if we attempt to run this code as it is.

i.e. the program crashes as a result of negative string length. This can be fixed easily however – read on!

Resolution

To fix that string length error as described above, simply add a one-line statement within the while loop to re-initialise the string s at the beginning of each loop.

Again, assuming we wish to use the hcat function to concatenate the following (left and right) vectors:

When the hcat function is invoked, the following tables summarise what happens:

Below shows what happens if we attempt to run this corrected code – it should run smoothly as expected.

The Project

To wrap up the source and header files that I use to test my codes.

C++ Source File List

• main.cpp
• frame.cpp
• hcat.cpp
• vcout.cpp

C++ Header File List

• frame.h
• hcat.h
• vcout.h

C++ Source Files

main.cpp

#include <iostream>  // cin, cout, endl, getline
#include <vector>    // vector
#include <string>    // string
#include "frame.h"   // width, frame
/*#include "vcat.h"    // vcat */
#include "hcat.h"    // hcat
#include "vcout.h"   // vcout

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

int main()
{

    string line1;            // line
    vector<string> para1;    // paragraph
    cout << "define vector<string> para1 below..." << endl;
    // read multiple lines to make a paragraph
    while (getline(cin, line1))
        para1.push_back(line1);
    cin.clear();

    string line2;            // line
    vector<string> para2;    // paragraph
    cout << "define vector<string> para2 below..." << endl;
    // read multiple lines to make a paragraph
    while (getline(cin, line2))
        para2.push_back(line2);
    cin.clear();

    cout << "-----------------------------------------------------\n"
            "Display: hcat(para1, para2)                          \n"
            "-----------------------------------------------------\n";
    vcout(hcat(para1, para2));

    return 0;
}

frame.cpp

#include <string>      // string
#include <vector>      // vector
#include <algorithm>   // max

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

string::size_type width(const vector<string>& v)
{
    string::size_type maxlen = 0;
    for(vector<string>::size_type i = 0; i != v.size(); ++i)
        maxlen = max(maxlen, v[i].size());
    return maxlen;
}

vector<string> frame(const vector<string>& v)
{
    vector<string> ret;
    string::size_type maxlen = width(v);
    string border(maxlen + 4, '*');

    // write the top border
    ret.push_back(border);

    // write each interior row, bordered by an asterisk and a space
    for (vector<string>::size_type i = 0; i != v.size(); ++i)
        ret.push_back("* " + v[i] + string(maxlen - v[i].size(), ' ') + " *");

    // write the bottom border
    ret.push_back(border);

    return ret;
}

hcat.cpp

#include <string>      // string
#include <vector>      // vector
#include "frame.h"     // width

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

vector<string> hcat(const vector<string>& left, const vector<string>& right)
{
    vector<string> ret;

    // add 1 to leave a space between pictures
    string::size_type width1 = width(left) + 1;

    // indices to look at elements from left and right respectively
    vector<string>::size_type i = 0, j = 0;

    string s;
    // continue until we've seen all rows from both pictures
    while (i != left.size() || j != right.size())
    {
        // construct new string to hold characters from both pictures
        //string s;
        s = "";

        // copy a row from the left-hand side, if there is one
        if (i != left.size())
            s = left[i++];

        // pad to full width
        s += string(width1 - s.size(), ' ');

        // copy a row from the right-hand side, if there is one
        if (j != right.size())
            s += right[j++];

        // add s to the picture we are creating
        ret.push_back(s);
    }

    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;
}

C++ Header Files

frame.h

#ifndef GUARD_FRAME_H
#define GUARD_FRAME_H

#include <string>
#include <vector>

std::string::size_type width(const std::vector<std::string>&);
std::vector<std::string> frame(const std::vector<std::string>&);

#endif // GUARD_FRAME_H

hcat.h

#ifndef GUARD_HCAT_H
#define GUARD_HCAT_H

#include <string>
#include <vector>

std::vector<std::string> hcat(const std::vector<std::string>&, const std::vector<std::string>&);

#endif // GUARD_HCAT_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

Conclusion

For the hcat function to work, we must re-initialise the string s at the beginning of each loop, as illustrated above.

Reference

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