Accelerated C++ Solution to Exercise 7-5

Exercise 7-5

Reimplement the grammar program using a list as the data structure in which we build the sentence.

Solution

This exercise is somewhat similar to Exercise 5-2 / 5-3 / 5-4, in which our objective is to replace all the relevant vector with list.

Here is the solution strategy:

  1. Make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3) – i.e. the textbook Grammar / Generate Sentence program.
  2. Replace all the vector with list, in main.cpp, gen_sentence.cpp/.h, gen_aux.cpp/.h.

The main.cpp function

Start with the main program – we notice the:


#include <vector>

// Some codes....

using std::vector;

// Some codes....

vector<string> sentence = gen_sentence(grammar);

// Some codes....

vector<string>::const_iterator it = sentence.begin();

We simply need to replace all the vector with list.

Here we can see the return type of the function gen_sentence needs to be changed from vector<string> to list<string>.

The gen_sentence function

We need to replace all the vector with list in the gen_sentence.cpp (source file) and gen_sentence.h (header file).

gen_sentence.cpp


#include <vector>

// Some codes....

using std::vector;

// Some codes....

list<string> gen_sentence(const Grammar& g)
{
  list<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

gen_sentence.h


// Some codes....

#include <vector>

std::vector<std::string> gen_sentence(const Grammar&);

// Some codes....

From this we see that we may need to adjust the gen_aux function to cater for the vector-to-list change.

The gen_aux function

Looking at the gen_aux.cpp (source file) and gen_aux.h (header file) reveals that we need to replace the vector with list.

gen_aux.cpp


#include <vector>

// Some codes....

using std::vector;

// Some codes....

void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
  // Some codes....
}

gen_aux.h


// Some codes....

#include <vector>

void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&);

// Some codes....

The Project

Just simply make a copy of the entire project as per Solution to Exercise 7-0 (Part 3 / 3), and do the vector-to-list replacement as mentioned above.

i.e.  use the following (list version) files as replacement of the original  (vector version) files:

Source File List (to change)

  • main.cpp
  • gen_sentence.cpp
  • gen_aux.cpp

Header File List (to change)

  • gen_sentence.h
  • gen_aux.h

Source Files (to change)

main.cpp


#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <list>              // std::list

#include "read_grammar.h"    // read_grammar
#include "gen_sentence.h"    // gen_sentence

#include <ctime>             // Added. std::time
#include <cstdlib>           // Added. std::srand

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

using std::srand;
using std::time;

int main()
{
  // Uncomment thhe below srand() to seed new randomness in new job-runs.
  // srand(time(NULL));

  Grammar grammar = read_grammar(cin);

  for (int i = 0; i != 5; ++i) {

    // generate the sentence
    list<string> sentence = gen_sentence(grammar);

    // write the first word, if any
    list<string>::const_iterator it = sentence.begin();
    if (!sentence.empty()) {
      cout << *it;
      ++it;
    }

    // write the rest of the words, each preceded by a space
    while (it != sentence.end()) {
      cout << " " << *it;
      ++it;
    }

    cout << endl;
  }

  return 0;
}

gen_sentence.cpp


#include <list>             // std::list
#include <string>             // std::string
#include "read_grammar.h"     // Grammar
#include "gen_aux.h"          // gen_aux

using std::list;
using std::string;

// Generate a sentence based on a Grammer object
// (S7.4.3/132)
list<string> gen_sentence(const Grammar& g)
{
  list<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

gen_aux.cpp


#include <string>            // std::string
#include <list>              // std::list
#include <stdexcept>         // logic_error

#include "read_grammar.h"    // Grammar, Rule, Rule_collection
#include "bracketed.h"       // bracketed
#include "nrand.h"           // nrand

using std::string;
using std::list;
using std::logic_error;

// Look up the input Grammar, and expand
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, list<string>& ret)
{
  if (!bracketed(word)) {
    ret.push_back(word);
  } else {
    // locate the rule that corresponds to word
    Grammar::const_iterator it = g.find(word);
    if (it == g.end())
      throw logic_error("empty rule");

    // fetch the set of possible rules
    const Rule_collection& c = it->second;

    // from which we select one at random
    const Rule& r = c[nrand(c.size())];

    // recursively expand the selected rule
    for (Rule::const_iterator i = r.begin(); i != r.end(); ++i)
      gen_aux(g, *i, ret);
  }
}

gen_sentence.h


#ifndef GUARD_GEN_SENTENCE_H
#define GUARD_GEN_SENTENCE_H

// gen_sentence.h

#include <string>            // std::string
#include <list>              // std::list
#include "read_grammar.h"    // Grammar

std::list<std::string> gen_sentence(const Grammar&);

#endif // GUARD_GEN_SENTENCE_H

gen_aux.h


#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

#include <string>             // std::string
#include <list>               // std::list
#include "read_grammar.h"     // Grammar

void gen_aux(const Grammar&, const std::string&, std::list<std::string>&);

#endif // GUARD_GEN_AUX_H

Test Program

Following replace all the vector-to-list replacements, and resubmit the program with the same input, we get the results as expected. In my case:

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>
^Z
the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Reference

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

Accelerated C++ Solution to Exercise 7-4

Exercise 7-4

The output produced by the cross-reference program will be ungainly if the input file is large. Rewrite the program to break up the output if the lines get too long.

Background

The original cross-reference program as per Solution to Exercise 7-0 (Part 2 / 3) lacks control in terms of output line length. For example, if my input “article” contains tons of repeated words, such as this:

apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple
orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange
orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange orange
orange orange orange orange orange orange orange
banana banana banana
banana
banana banana banana
banana banana
banana banana banana banana banana banana banana
banana banana
apple apple apple apple apple apple apple apple apple apple apple apple apple apple
apple apple apple apple apple apple apple apple apple apple apple apple apple apple
apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple apple

Given the above input, the default program produces output summary like this:

apple occurs on line(s): 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13
banana occurs on line(s): 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 10
orange occurs on line(s): 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 3, 4, 4, 4, 4, 4, 4, 4

The output lines may become very long – i.e. user may need to scroll left and right to see all the line numbers (not very user friendly). A bit “ungainly” as suggested by the author.

This therefore motivates us to add a control in place that ensures the output line length never exceeds a pre-defined value. i.e. if we set max line length to be 30 characters, and the output result contains 100 characters, the program should be able to split into 4 lines (first 3 lines contain 30 characters, and the 4th line contains 10 characters). This way, the user won’t need to scroll left and right to see all line numbers – more user friendly.

The following section will describe a solution to this problem.

Solution

This is our solution strategy:

  1. Make a copy of the project (i.e. source and header files) as per Solution to Exercise 7-0 (Part 2 / 3).
  2. Update the main program to incorporate the desirable line-length control.

Incorporate Line-length Control

First of all, we need define a const string::size_type lineLength, which is the maximum line-length of the output.

We then need to have a means to concatenate various output values.

In the Solution to Exercise 5-1, we learnt that the variable type std::ostringstream (of <sstream>  directive) is way more superior in concatenation in comparison to std::string (of <string> directive). i.e. there seem to be much less constraints in terms of concatenating values of different types for a std::ostringstream than std::string. For this reason, we shall use std::ostringstream to store output. Note also that ostreamstring can be converted into a string easily.

When displaying the line numbers for each word, we implement a if-condition to ensure the line length doesn’t exceed our pre-defined lineLength. The modulus operator (%) will come in handy for this.

The Project

Just simply re-use the entire project from Solution to Exercise 7-0 (Part 2 / 3), and replace the main program with the following. (Note that for illustration sake the pre-defined lineLength is set to 60 characters max per line).


#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include <sstream>    // std::ostringstream
#include "xref.h"     // xref

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

// Find all the lines that refer to each word in the input
// (S7.3/128)
int main()
{
  // Call xref using split by default.
  map<string, vector<int> > ret = xref(cin);

  // Set the width of output line to this max width limit.
  const string::size_type lineLength = 60;

  // Write the results.
  for (map<string, vector<int> >::const_iterator it = ret.begin();
       it != ret.end(); ++it) {

    // We use ostreamstring for its powerful concatenation properties.
    // We can pretty much concatenate anything to an ostreamstring, in
    // comparison to string.
    ostringstream outputStream;

    // Write the word
    outputStream << it->first << " occurs on line(s): ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    outputStream << *line_it;
    ++line_it;

    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      outputStream << ", " << *line_it;
      ++line_it;
    }

    // Break outputStream into multiple lines with max width of lineLength.
    string outputLine = outputStream.str();
    for (string::size_type i = 0; i != outputLine.size(); ++i ) {
      if (i % lineLength == 0) {
        cout << endl;
      }
      cout << outputLine[i];
    }

    // Write a new line to separate each word from the next.
    cout << endl;
  }

  return 0;
}

Test Program

Re-submitting the same input (see the top of this post), our output now looks much more “controlled”, in terms of line length.


apple occurs on line(s): 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1
1, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 1
2, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 1
3, 13, 13, 13, 13, 13, 13, 13, 13, 13

banana occurs on line(s): 5, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 9
, 9, 9, 9, 9, 10, 10

orange occurs on line(s): 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2
, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3
, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4
, 4

Not perfect, but better.

Reference

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

Accelerated C++ Solution to Exercise 7-3

Exercise 7-3

The cross-reference program from S7.3/126 could be improved: As it stands, if a word occurs more than once on the same input line, the porgram will report that line multiple times. Change the code so that it detects multiple occurences of the same line number and inserts the line number only once.

Background

Remember that when we run the Chapter 7 cross-reference program (i.e. Solution to Exercise 7-0 (Part 2 / 3) ), we have the following test results:

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2, 2

Note:

  1. Recall that the xref program assumes the first line as line 1 (instead of 0), second line as line 2 (instead of 1). This is as designed.
  2. The word “orange” appears on line 2 twice. So when it comes to being displayed in the summary, it shows the line number “2” twice.
  3. The objective of this exercise is to only store non-duplicated line number.

Solution Strategy

We only need to make a very small enhancement – to adjust the xref function by adding a small bit of code. Include a if condition to check whether the line number already exists for the corresponding associative array. Use the find utility of the <algorithm> directive to help us do this.

The Project

We can reuse the entire project as per Solution to Exercise 7-0 (Part 2 / 3). Simply replace the xref.cpp file with this new one:

xref.cpp


#include <iostream>   // std::cin, std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include <algorithm>  // std::find
#include "split.h"    // split


using std::cin;
using std::map;
using std::string;
using std::vector;
using std::istream;
using std::find;

// Find all the lines that refer to each word in the input
// In this program, the first line is represented by line 1,
// second line is represented by line 2, etc.
// (S7.3/126)
// Adjusted as per Exercise 7-3: store only non-duplicated line numbers.
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
  string line;
  int line_number = 0;
  map<string, vector<int> > ret;  // map string to vector<int>

  // Read the next line
  while (getline(in, line)) {
    ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it) {

      // store only non-duplicated line numbers.
      if ( find( ret[*it].begin(), ret[*it].end(), line_number) == ret[*it].end() )
        ret[*it].push_back(line_number);
    }
  }

  return ret;
}

Test Program

Re-submitting the program with the same input, the program now produces non-duplicated line numbers per associative array (word).

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2

Reference

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

Accelerated C++ Solution to Exercise 7-2

Exercise 7-2

Extend the program in S4.2.3/64 to assign letter grades by ranges:

A 90-100
B 80-89.99...
C 70-79.99...
D 60-69.99...
F < 60

Solution

The strategy:

  1. Make a copy of the entire projects from Solution to Exercise 4-0. (i.e. the sample programs in Chapter 4 of the textbook).
  2. Write a new home-made getLetterGrade function that returns a string letterGrade given an input (numeric) double grade, using if/else condition.
  3. In the main program, use the getletterGrade function to compute the student’s string letterGrade. Have an associative array letterGradeCount that maps a string (letter grade) to integer (to keep track of letter grade occurrences).

The Program

Here summarises the entire Code::Block Project, including the header and source files.

Acpp7p2MgntTree

Source File List

Header File List

Source Files

main.cpp


#include <algorithm>
#include <iomanip>
#include <ios>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>
#include <map>
#include "grade.h"
#include "Student_info.h"
#include "getLetterGrade.h"

using std::cin;
using std::cout;
using std::endl;
using std::domain_error;
using std::max;
using std::setprecision;
using std::sort;
using std::streamsize;
using std::string;
using std::vector;
using std::map;

int main()
{
  vector<Student_info> students;
  Student_info record;
  string::size_type maxlen = 0;   // the length of the longest name

  // read and store all the student's data.
  // Invariant:   students contain all the student records read so far
  //              maxlen contains the length of the longest name in students
  while (read(cin, record))
  {
    // find the length of longest name
    maxlen = max(maxlen, record.name.size());
    students.push_back(record);
  }

  // alphabetize the student records
  sort(students.begin(), students.end(), compare);

  // write the names and grades
  map<string, int> letterGradeCount;   // To store letter grade occurrences.
  for (vector<Student_info>::size_type i = 0;
       i != students.size(); ++i)
  {
    //write the name, padded on teh right to maxlen + 1 characters
    cout << students[i].name
         << string(maxlen + 1 - students[i].name.size(), ' ');

     //compute and write the grade
    try
    {
      double final_grade = grade(students[i]);
      string letterGrade = getLetterGrade(final_grade);
      letterGradeCount[letterGrade]++;         // Count Letter Grades.
      streamsize prec = cout.precision();
      cout << setprecision(3) << final_grade
           << setprecision(prec) << " (" << letterGrade << ")";
    }
    catch (domain_error e)
    {
      cout << e.what();
    }
    cout << endl;
  }
  // Display letter grade summary
  cout << "\nLetter Grade Summary" << endl;
  for (map<string, int>::const_iterator i = letterGradeCount.begin();
      i != letterGradeCount.end(); ++i)
    cout << i->first << ": " << i->second << endl;

  return 0;
}

getletterGrade.cpp


#include <string>

using std::string;

// Convert a numeric grade into a letter grade.
// (For Exercise 7-2)
string getLetterGrade(double grade) {

  string ret;

  if (grade >= 90.0)
    ret = "A";
  else if (grade >= 80.0 && grade < 90.0)
    ret = "B";
  else if (grade >= 70.0 && grade < 80.0)
    ret = "C";
  else if (grade >= 60.0 && grade < 70.0)
    ret = "D";
  else
    ret = "F";

  return ret;
}

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

Student_info.cpp


#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

</p>

Header Files

getletterGrade.h

#ifndef GUARD_GETLETTERGRADE_H
#define GUARD_GETLETTERGRADE_H

// getLetterGrade.h

#include <string>

std::string getLetterGrade(double);

#endif // GUARD_GETLETTERGRADE_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 - final version
#include <vector>
double median(std::vector<double>);

#endif // GUARD_MEDIAN_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 test the program by submitting a list of sample student grades. The program automatically compute and display the numeric and letter grades. It also creates a letter grade summary to count occurances per letter grade.

johnny   90 90 90 90 90
jason    85 85 85 85 85
billy    82 82 82 82 82
fred     80 80 80 80 80
frank    70 70 70 70 70
jay      66 66 66 66 66
bob      60 60 60 60 60
mary     50 50 50 50 50
ann      40 40 40 40 40
bill     30 30 30 30 30
goat     10 10 10 10 10
dog      0  0  0  0  0
^Z
^Z
ann    40 (F)
bill   30 (F)
billy  82 (B)
bob    60 (D)
dog    0 (F)
frank  70 (C)
fred   80 (B)
goat   10 (F)
jason  85 (B)
jay    66 (D)
johnny 90 (A)
mary   50 (F)

Letter Grade Summary
A: 1
B: 3
C: 1
D: 2
F: 5

Reference

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

Accelerated C++ Solution to Exercise 7-1

Exercise 7-1

Extend the program from S7.2/124 to produce its output sorted by occurrence count. That is, the output should group all the words that occur once, followed by those that occur twice, and so on.

Solution

The strategy:

  1. Start with the program from S7.2/124. i.e. The main program in Solution to Exercise 7-0 (Part 1 / 3).
  2. Have a new (associative array) map<int, vector<string> > wordsByFreq to map int (word occurring frequency) to vector<string> (all the words at that occurring frequency). The key of this map is essentially the int frequency. In other words, this map is by default sort by the int frequency (as it is the key to this map).
  3. We populate the map<string, int> counters as usual. Once it is fully populated, we use it to populate our wordsByFreq.
  4. Once the wordsByFreq is fully populated, we use it to display all the words grouped by frequency.

The Program

The program is surprisingly easy to write / extend. As long as we know what a map is and how it works, this program should be fairly easy to understand.

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector

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

int main()
{
  string s;
  map<string, int> counters;                // Store each word and an
                                            // associated counter
  map<int, vector<string> > wordsByFreq;    // Store all the words for
                                            // each frequency

  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];

  cout << "\nDisplay words and associating frequency." << endl;
  // write the words and associated counts
  for (map<string, int>::const_iterator i = counters.begin();
       i != counters.end(); ++i) {
    cout << i->first << "\t" << i->second << endl;

    // Obtain words by frequency
    wordsByFreq[i->second].push_back(i->first);
  }

  // Display words by frequency
  cout << "\nDisplay words grouped by frequency." << endl;
  for (map<int, vector<string> >::const_iterator i = wordsByFreq.begin();
       i != wordsByFreq.end(); ++i) {
    cout << "\nFrequency: " << i->first << endl;

    for (vector<string>::const_iterator j = i->second.begin();
         j != i->second.end(); ++j)
      cout << *j << endl;

  }

  return 0;
}

Test Program

I am going to submit the same set of test input as per the word counting program of Solution to Exercise 7-0 (Part 1 / 3). The result looks correct.

apple orange banana
orange orange
apple banana
mango
^Z

Display words and associating frequency.
apple   2
banana  2
mango   1
orange  3

Display words grouped by frequency.

Frequency: 1
mango

Frequency: 2
apple
banana

Frequency: 3
orange

Reference

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

Accelerated C++ Solution to Exercise 7-0

Exercise 7-0

Compile, execute, and test the programs in this chapter.

Solution

In Chapter 7 of the textbook there are 3 core concepts / programs introduced. For ease of documentation I shall dice this up into 3 parts as followings – simply click the hyperlink to drill down to see the post corresponding to the particular part.

Exercise 7-0 (Part 1 / 3): The Count-word Program.Relating to section 7.2 of the textbook (page 124-126). Use associative arrays to count words – in this particular exercise, we shall use the map from the standard library.

Exercise 7-0 (Part 2 / 3): The Cross-reference Program. Relating to section 7.3 of the textbook (page 126-129). Use associative arrays to find all the lines that refer to each word in the input.

Exercise 7-0 (Part 3 / 3): The Gen-sentence Program. Relating to section 7.4 of the textbook (page 129-136). One of my personal favourite. Use a combination of associative arrays and random number generator to generate a set of random sentences, based on a set of predefined Grammar Rules.

Reference

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

Accelerated C++ Solution to Exercise 7-0 (Part 3 / 3)

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

Exercise Exercise 7-0 (Part 3 / 3)

Use a combination of associative arrays and random number generator to generate a set of random sentences, based on a set of predefined Grammar Rules.

Background

This is one of my current favourite exercise – quite hard to understand at first, but once you’ve got it, all becomes so clear (and that burst of satisfying laughter when things clicked in the end – “Wow this is so cool!”). This exercise is about generating a random sentence, based on an input “Grammar” definition that we provide to the program. The input Grammar definition table (as per S7.4/129) is displayed below – column 1 lists the categories, and column 2 the corresponding rules.

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>

The program generates a random sentence based on the category “<sentence>” – it then recursively expand the associating rules in a “random” manner.

My aim of this post is to summarise all the C++ source and header files (in the form of a complete Code::Block project), run the program, and confirms that the program works as expected. As Andrew Koeing / Barbara Moo (Authors of the book) have already gone through a great deal on explaining how this entire program works, I believe it is appropriate, rather than repeat explaining how this program works here, to just simply suggest to refer to the text book – see Section 7.4 (Page 129) for the detail explanation.

A Note on Random Number Generator

The source code nrand.cpp contains a very clever approach to generate a random number within a desirable range in an evenly distributed manner. The Author has compared this approach with an alternative “not-as-good” approach that uses modulus – % (which generate random number in a non-evenly distributed manner. i.e. some random number are “more likely” than the others.). See S7.4.4/135 for details. One thing to note is that the code uses rand() – i.e. running the program 100 times result in generating the same set of “random” results. This feature actually is as designed – as it enables the program easier to debug. Only when the program is fully tested, we then add a srand() at the top of the program ti make the whole thing to appear even more “random” – i.e. the results in multiple program run are likely to differ.

In this post I will include two main programs – one without the srand (like the example in the book – so each job run gives the same set of random results), and one with the srand (to show that results can differ from multiple job run). The srand() “seeds” a new form of randomness every time when the program is run – dependent on the system clock time.

In addition, there are many “C++ Random Number Generator” related article online (a simple Google search will return lots of good articles). I have found a few that are quite interesting – but all in all, I think all these solutions eventually sort of converge back to the method described by the Accelerated C++ text book!

The Project

Here wraps up all the source codes that I use – I have modified the original main program by adding a for loop – so instead of creating just one sentence, it generates multiple sentences – to demonstrate / give us a better “feel” on randomness. I have included here two main programs – one without a srand(), and the other with a srand(). I shall test both main programs accordingly – but effectively, the one without srand() will create the same set of “random results” in every job run. Whereas the one with the srand() will create different sets of “random results” in every job run.

Source File List

Header File List

Source Files

main.cpp

(Simply uncomment the srand() for Test 2 – with srand)

#include <iostream>          // std::cin, std::cout, std::endl
#include <string>            // std::string
#include <vector>            // std::vector

#include "read_grammar.h"    // read_grammar
#include "gen_sentence.h"    // gen_sentence

#include <ctime>             // Added. std::time
#include <cstdlib>           // Added. std::srand

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

using std::srand;
using std::time;

int main()
{
  srand(time(NULL));   // Added. Seed new form of randomness.

  Grammar grammar = read_grammar(cin);

  for (int i = 0; i != 100; ++i) {

    // generate the sentence
    vector<string> sentence = gen_sentence(grammar);

    // write the first word, if any
    vector<string>::const_iterator it = sentence.begin();
    if (!sentence.empty()) {
      cout << *it;
      ++it;
    }

    // write the rest of the words, each preceded by a space
    while (it != sentence.end()) {
      cout << " " << *it;
      ++it;
    }

    cout << endl;
  }

  return 0;
}

bracketed.cpp

#include <string>     // std::string

using std::string;

// Determine whether a string is surrounded by brackets <>
// (S7.4.3/132)
bool bracketed(const string& s)
{
  return s.size() > 1 &&
         s[0] == '<' &&
         s[s.size() - 1] == '>';
}

gen_aux.cpp

#include <string>            // std::string
#include <vector>            // std::vector
#include <stdexcept>         // logic_error

#include "read_grammar.h"    // Grammar, Rule, Rule_collection
#include "bracketed.h"       // bracketed
#include "nrand.h"           // nrand

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

// Look up the input Grammar, and expand
// (S7.4.3/132)
void gen_aux(const Grammar& g, const string& word, vector<string>& ret)
{
  if (!bracketed(word)) {
    ret.push_back(word);
  } else {
    // locate the rule that corresponds to word
    Grammar::const_iterator it = g.find(word);
    if (it == g.end())
      throw logic_error("empty rule");

    // fetch the set of possible rules
    const Rule_collection& c = it->second;

    // from which we select one at random
    const Rule& r = c[nrand(c.size())];

    // recursively expand the selected rule
    for (Rule::const_iterator i = r.begin(); i != r.end(); ++i)
      gen_aux(g, *i, ret);
  }
}

gen_sentence.cpp

#include <vector>             // std::vector
#include <string>             // std::string
#include "read_grammar.h"     // Grammar
#include "gen_aux.h"          // gen_aux

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

// Generate a sentence based on a Grammer object
// (S7.4.3/132)
vector<string> gen_sentence(const Grammar& g)
{
  vector<string> ret;
  gen_aux(g, "<sentence>", ret);
  return ret;
}

nrand.cpp

#include <stdexcept>    // std::domain_error
#include <cstdlib>      // rand(), RAND_MAX

using std::domain_error;
using std::rand;


// return a random integer in the range [0, n)
// (S7.4.4/135)
int nrand(int n)
{
  if (n <= 0 || n > RAND_MAX)
    throw domain_error("Argument to nrand is out of range");

  const int bucket_size = RAND_MAX / n;
  int r;

  do r = rand() / bucket_size;
  while (r >= n);

  return r;
}

read_grammar.cpp

#include "read_Grammar.h"    // Grammar, Rule
#include <istream>           // std::istream
#include <string>            // std::string
#include <vector>            // std::vector
#include "split.h"           // split

using std::istream;
using std::string;
using std::vector;
using std::map;

// Read a Grammar from a given input stream
// (S7.4.1/131)
Grammar read_grammar(istream& in)
{
  Grammar ret;
  string line;

  // read the input
  while (getline(in, line)) {

    // split the input into words
    vector<string> entry = split(line);

    if (!entry.empty())
      // use the category to store the associated rule
      ret[entry[0]].push_back(Rule(entry.begin() + 1, entry.end()));

  }
  return ret;
}

split.cpp

#include <string>    // string
#include <vector>    // vector
#include <cctype>    // isspace
#include <algorithm>  // find_if

using std::vector;
using std::string;
using std::isspace;
using std::find_if;

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

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

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

  iter i = str.begin();
  while (i != str.end()) {

    // 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;
  }
  return ret;
}

Header Files

bracketed.h

#ifndef GUARD_BRACKETED_H
#define GUARD_BRACKETED_H

// bracketed.h

#include <string>

bool bracketed(const std::string&);

#endif // GUARD_BRACKETED_H

gen_aux.h

#ifndef GUARD_GEN_AUX_H
#define GUARD_GEN_AUX_H

// gen_aux.h

#include <string>             // std::string
#include <vector>             // std::vector
#include "read_grammar.h"     // Grammar

void gen_aux(const Grammar&, const std::string&, std::vector<std::string>&);

#endif // GUARD_GEN_AUX_H

gen_sentence.h

#ifndef GUARD_GEN_SENTENCE_H
#define GUARD_GEN_SENTENCE_H

// gen_sentence.h

#include <string>            // std::string
#include <vector>            // std::vector
#include "read_grammar.h"    // Grammar

std::vector<std::string> gen_sentence(const Grammar&);

#endif // GUARD_GEN_SENTENCE_H

nrand.h

#ifndef GUARD_NRAND_H
#define GUARD_NRAND_H

// nrand.h

int nrand(int);

#endif // GUARD_NRAND_H

read_grammar.h

#ifndef GUARD_READ_GRAMMAR_H
#define GUARD_READ_GRAMMAR_H

// read_grammar.h

#include <vector>      // std::vector
#include <string>      // std::string
#include <map>         // std::map
#include <istream>     // std::istream

typedef std::vector<std::string> Rule;
typedef std::vector<Rule> Rule_collection;
typedef std::map<std::string, Rule_collection> Grammar;

Grammar read_grammar(std::istream&);

#endif // GUARD_READ_GRAMMAR_H

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

// split.h

#include <vector>
#include <string>

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

#endif // GUARD_SPLIT_H

Test Program

I have two set of tests. Test 1 uses main.cpp (without srand), and Test 2 uses main.cpp (with srand). For each test, I shall submit the same Grammar rules:

<noun>          cat
<noun>          dog
<noun>          table
<noun-phrase>   <noun>
<noun-phrase>   <adjective> <noun-phrase>
<adjective>     large
<adjective>     brown
<adjective>     absurd
<verb>          jumps
<verb>          sits
<location>      on the stairs
<location>      under the sky
<location>      wherever it wants
<sentence>      the <noun-phrase> <verb> <location>

Test 1 – main.cpp (without srand)

Because this version does not has a srand() at the top, each usage of rand() relies on the same “seed” – i.e. same set of “random results” in every job run.

Job-run 0

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Job-run 1

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Job-run 2

the large brown dog sits wherever it wants
the table sits under the sky
the cat jumps on the stairs
the brown cat jumps under the sky
the brown large brown cat sits wherever it wants

Test 2 – main.cpp (with srand)

Because this version has a srand() at the top, each usage of rand() relies on the a new “seed” – i.e. new set of “random results” in every job run. All subsequent job runs may produce differnt results.

Job-run 0

the dog jumps wherever it wants
the brown cat jumps under the sky
the cat jumps on the stairs
the brown absurd large table sits wherever it wants
the table jumps under the sky

Job-run 1

the table sits under the sky
the cat sits under the sky
the absurd brown table sits on the stairs
the brown absurd large absurd large table jumps under the sky
the brown table sits wherever it wants

Job-run 2

the dog sits wherever it wants
the absurd dog jumps under the sky
the table sits wherever it wants
the absurd cat sits under the sky
the dog jumps on the stairs

Reference

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

Accelerated C++ Solution to Exercise 7-0 (Part 2 / 3)

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

Exercise 7-0 (Part 2 / 3)

Use associative arrays to find all the lines that refer to each word in the input. As per S7.3/126.

Solution

Section 7.3 (Page 126) introduces a method to find all the lines that refer to each word in the input, with the aid of associative arrays. This is so called a “Cross Reference Table”. See the text book for detail description.

Special Note on Line Number

Note that the cross-reference program (xref) as presented by the author of the book uses line 1 to represent the first line (instead of line 0). Likewise, line 2 to represent the second line (instead of line 1). i.e. the line number is always “one more” in comparison to our index system in which index 0 represents the first item.

But then I guess it makes sense as in most editor (like Microsoft Word), whenever we search for a line, it makes more sense from a human perspective that line 1 represents the first line, etc.

Just something to bear in mind – as it is likely that we switch between using 0 or 1 to represent the first line, depending on the problem / application that we are facing.

The Project

Here wrap up the project showing all the source and header files Used.

Acpp7p0p2MgntTree

Source File List

Header File List

Source Files

main.cpp

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "xref.h"     // xref

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

// Find all the lines that refer to each word in the input
// (S7.3/128)
int main()
{
  // Call xref using split by default.
  map<string, vector<int> > ret = xref(cin);

  // Write the results.
  for (map<string, vector<int> >::const_iterator it = ret.begin();
       it != ret.end(); ++it) {

    // Write the word
    cout << it->first << " occurs on line(s): ";

    // Followed by one or more line numbers.
    vector<int>::const_iterator line_it = it->second.begin();
    cout << *line_it;   // write the first line number

    ++line_it;
    // Write the rest of the line numbers, if any.
    while (line_it != it->second.end()) {
      cout << ", " << *line_it;
      ++line_it;
    }
    // Write a new line to separate each word from the next.
    cout << endl;
  }

  return 0;
}

split.cpp

#include <string>    // string
#include <vector>    // vector
#include <cctype>    // isspace
#include <algorithm>  // find_if

using std::vector;
using std::string;
using std::isspace;
using std::find_if;

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

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

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

  iter i = str.begin();
  while (i != str.end()) {

    // 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;
  }
  return ret;
}

xref.cpp

#include <iostream>   // std::cin, std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "split.h"    // split

using std::cin;
using std::map;
using std::string;
using std::vector;
using std::istream;

// Find all the lines that refer to each word in the input
// (S7.3/126)
map<string, vector<int> >
xref(istream& in, vector<string> find_words(const string&) = split)
{
  string line;
  int line_number = 0;
  map<string, vector<int> > ret;  // map string to vector<int>

  // Read the next line
  while (getline(in, line)) {
    ++line_number;

    // Break the input line into words
    vector<string> words = find_words(line);

    // remember that each word occurs on the current line
    for (vector<string>::const_iterator it = words.begin();
         it != words.end(); ++it)
      ret[*it].push_back(line_number);
  }

  return ret;
}

Header Files

split.h

#ifndef GUARD_SPLIT_H
#define GUARD_SPLIT_H

#include <vector>
#include <string>

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

#endif // GUARD_SPLIT_H

xref.h

#ifndef GUARD_XREF_H
#define GUARD_XREF_H

// xref.h

#include <iostream>   // std::istream
#include <map>        // std::map
#include <string>     // std::string
#include <vector>     // std::vector
#include "split.h"      // split

std::map<std::string, std::vector<int> >
xref(std::istream&,
     std::vector<std::string> find_words(const std::string&) = split);

#endif // GUARD_XREF_H

Test Program

I now submit some words to the console input upon running the program. The program quickly identify the line numbers (that each word resides) and display results as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on line(s): 1, 3
banana occurs on line(s): 1, 3
mango occurs on line(s): 4
orange occurs on line(s): 1, 2, 2

Reference

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

Accelerated C++ Solution to Exercise 7-0 (Part 1 / 3)

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

Exercise 7-0 (Part 1 / 3)

Use associative arrays to count words – in this particular exercise, we shall use the map from the standard library.

Solution

Section 7.2 (Page 124) of the textbook contains a very nice and compact main function that performs easy word counting with associating arrays using the map utility. The program is very easy to understand. See the text book for detail description.

#include <iostream>   // std::cin, std::cout, std::endl
#include <map>        // std::map
#include <string>     // std::string

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

int main()
{
  string s;
  map<string, int> counters;  // store each word and an associated counter

  // read the input, keeping track of each word and how often we see it
  while (cin >> s)
    ++counters[s];

  // write the words and associated counts
  for (map<string, int>::const_iterator it = counters.begin();
       it != counters.end(); ++it)
    cout << it->first << "\t" << it->second << endl;

  return 0;
}

Test Program

I now submit some words to the console input upon running the program. The program quickly counts the words and display results as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple   2
banana  2
mango   1
orange  3

One more thing to note is that the associative array automatically sort the key of the key-value pair. i.e. the pair<const K, V>.

Reference

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

Accelerated C++ Solution to Exercise 6-9

Exercise 6-9

Use a library algorithm to concatenate all the elements of a vector<string>.

Solution

In Chapter 6, the author introduces the accumulate algorithm which enables easy summation of all numeric elements within a vector<double>.

If you look at section 6.5 (page 121 of the book), the accumulate function takes this form: accumulate(b, e, t), in which arguments b and e defines the asymmetric range [b, e) of the vector elements to be subject for the summation. the argument t represents the initial value of the summation and implies the type the accumulation.

For instance, if we wish to sum all the elements within the vector<double> numbers, with the initial value of 0.0, the summation is computed as accumulate(numbers.begin(), numbers.end(), 0.0).

To concatenate all the elements of a vector<string>, interestingly, we can also leverage this accumulate function.

For instance, if we wish to sum (concatenate) all the elements within the vector<string> words, with the initial value of “” (implies empty vector), the concatenation is computed as accumulate(words.begin(), words.end(), “”). i.e. concatenating all the string elements will give us a giant (longer) string. (It’s an overload!)

Test Program

Fortunately, this concept can be tested out easily by submitting the following very simple main program. One realisation is that the accumulate function is actually under the <numeric> directive, not the <algorithm> directive as I had originally thought.

#include <iostream>    // cout, endl;
#include <vector>      // vector
#include <string>      // string
#include <numeric>     // accumulate

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

int main () {
    string s = "abc";
    vector<string>  vec (20, s);
    string sentence = accumulate( vec.begin(), vec.end(), string("") );
    cout << sentence << endl;
}

Result

Running the main program confirms that the concatenation can be performed using the accumulate algorithm. i.e. the 20 elements of string “abc” have been concatenated into one giant string element.

abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc

Process returned 0 (0x0)   execution time : 0.394 s
Press any key to continue.

Reference

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