Exercise 7-7

Change the driver for the cross-reference program so that it writes line if there is only one line and lines otherwise.

Solution

The solution to this exercise is surprisingly simple. To clarify the question a bit – it essentially asks us to have some sort of if-else condition in place.

For instance…

• If the word “apple” occurs only on one line, we print “apple occurs on line: ” (followed by the line number).
• Otherwise, if the word “apple” occurs on multiple lines, we print “apple occurs on lines: ” (followed by the line numbers).

Recall that the Solution to Exercise 7-3 already provides the skeleton project that reports non-duplicated word occurrence line numbers. It therefore makes sense to use that project as the baseline project, and do the adjustment on top of it.

It turns out that there is only one small bit of code that needs changing, and it resides at the main.cpp file (the main function).

This is the original snippet within the main function:

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

We can change it easily to the following to achieve that if-else conditioning. We essentially resolves the number of non-duplicate line occurences for the word beforehand. We can then use it to construct the if-else logic and display either “line” or “lines” accordingly.

    // Find number of lines the word has appeared
    vector<int>::size_type numLines = (it->second).size();

    // Write the word
    cout << it->first << " occurs on ";
    if (numLines == 1)
      cout << "line: ";
    else
      cout << "lines: ";

Surprisingly simple.

The Project

Simply…

1. Re-use that Project as per Solution to Exercise 7-3.
2. Replace the main.cpp file as per followings.

#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) {

    // Find number of lines the word has appeared
    vector<int>::size_type numLines = (it->second).size();

    // Write the word
    cout << it->first << " occurs on ";
    if (numLines == 1)
      cout << "line: ";
    else
      cout << "lines: ";

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

Test Result

Running this new version main code gives us the result as expected.

apple orange banana
orange orange
apple banana
mango
^Z
apple occurs on lines: 1, 3
banana occurs on lines: 1, 3
mango occurs on line: 4
orange occurs on lines: 1, 2

Reference

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

Exercise 7-6

Reimplement the gen_sentence program using two vectors: One will hold the fully unwound, generated sentence, and the other will hold the rules and will be used as a stack. Do not use any recursive calls.

Solution

After spending hours scratching my head and still getting stuck on this question, I decided to turn to Google for help. Eventually I discovered this Github Solution Code (uploaded by the Author himself) to this exercise. For the sake of learning, I simply picked out the “bits and pieces” from the Author’s code (such as the core concepts and snippets) and integrated these to my own solution. So let me disclose this upfront – the solution that you are seeing in this page is a result of the great help and pointer from the Author himself. Nevertheless, I believe it is the right thing to do to at least try and understand how the core concept work. The mission of this post is to add some additional documentation to demonstrate that we actually understand the concepts and techniques presented by the Author.

In the followings, I shall:

1. Disclose the project (i.e. the C++ source and header files) that I use in my learning.
2. Test run the job to confirm that it works.
3. Demonstrate that we understand the new concept by manually draw out the step by step logic.

The Project

First, open the baseline project (i.e. the C++ source and header files) as per Solution to Exercise 7-0 (Part 3 / 3). Once the baseline project is opened up in (say) Code::Block, replace the following files with the newer version.

• gen_aux.h – use this newer version.
• gen_aux.cpp – use this newer version.
• gen_sentence.cpp – use this newer version.

Newer Version Souce and Header Files

This summarises the newer version source and header files.

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>&,
             std::vector<std::string>&);

#endif // GUARD_GEN_AUX_H

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
// (modified version of S7.4.3/132)
void gen_aux(const Grammar& g, const string& token,
       vector<string>& sentence, vector<string>& tokens) {
  if (!bracketed(token)) {
    sentence.push_back(token);
  } else {
    // locate the rule that corresponds to `token'
    Grammar::const_iterator it = g.find(token);

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

    // push rule's tokens onto stack of tokens
    // (in reverse order, because we're pushing and popping from the back)
    for (Rule::const_reverse_iterator i = r.rbegin(); i != r.rend(); ++i)
      tokens.push_back(*i);
  }
}

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 Grammar object
// (modified version of S7.4.3/132)
vector<string> gen_sentence(const Grammar& g) {
  vector<string> sentence;
  vector<string> tokens;
  tokens.push_back("<sentence>");

  while (!tokens.empty()) {
    string token = tokens.back();
    tokens.pop_back();
    gen_aux(g, token, sentence, tokens);
  }

  return sentence;
}

Test Result

Note: the result might differ when you run the job due to the nrand(). Core concept remains true though.

<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

Understanding the concept

Let’s use the first output sentence to illustrate our understanding of the core concept used by the gen_sentence and gen_aux functions.

the large brown dog sits wherever it wants

The billion dollar question, how did the program generate this line?

To demonstrate my understanding, I’ve manually put together a couple of simple Excel tables to walk through the logic.

Recall that this is the input grammar table:

The gen_sentence and gen_aux can give the following output values:

Some Notes To This Example

For some extra clarity, I include here a brief explanation of what each column means.

tokens non-empty?

If non-empty, the while loop inside the gen_sentence step would keep expanding tokens and construct the string sentence. Otherwise, the while loop stop and we have our sentence! (Note that we start by expanding the top level “<sentence>”)

vector<string> sentence;
vector<string> tokens;
tokens.push_back("<sentence>");
while (!tokens.empty()) {
    // some codes to expand <sentence> and construct the string sentence.
}
return sentence;

const string& token

This is the last element of tokens, implied by this statement within the gen_sentence step:

string token = tokens.back();

Is token bracketed?

If the token is bracketed, it implies the token corresponds to a Grammar category and need expanding. If it is not bracketed, we  simply append the text the the string sentence.

if (!bracketed(token)) {
    // some codes to construct the string sentence.
} else {
    // some codes to expand the token.
}

const Rule& r

If the token is bracketed (i.e. a Grammar category), the const Rule& r is essentially the Grammar rule. I highlight this in orange.

vector<string>& sentence

If the token is not bracketed, we simply append the text to the string sentence. This column shows what the constructed string sentence look like. I highlight the newly appended element in blue.

(Updated) vector<string>& tokens

This is the interesting part and is updated by a combination of the gen_sentence and gen_aux steps.

• The tokens.pop_back() statement remove the last element of tokens (hence the strike-through in the table).
• If token (i.e. the token column) is bracketed, the for loop within the gen_aux function appends the entire rule (highlighted in orange) in reverse order. This is a very clever technique to get the tokens expand and string sentence constructed in the expected order. (it’s easier to visualise this via the Excel table above instead of explaning in writing!).

Summary

Walking through the logic as illustrated in the Excel table, the program generates and return the complete string sentence. The actual sentence may get constructed differently due to the nrand().

Reference

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

The Github code solution uploaded by the author (A.Koening).