Questions with Accelerated C++ exercises of chapter 7

[Lambda]

7-4 The input file is a novel. There are more than 4, 000 'the' in the
text.
Breaking up the output will help? How to break up the output? Add
newlines?

7-5 Why use list? I can't see any benefit. List does not support
random accesses.
And there are several vectors:

Rule, Rule_collection, vector contains words the input split into,
vector populated by gen_aux, and vector gen_sentence returned

Which one should I replace with list?

7-9 It's a difficult one as author said.I have no idea.

 

[Christopher]

7-4 The input file is a novel. There are more than 4, 000 'the' in the
text.
Breaking up the output will help? How to break up the output? Add
newlines?

7-5 Why use list? I can't see any benefit. List does not support
random accesses.
And there are several vectors:

Rule, Rule_collection, vector contains words the input split into,
vector populated by gen_aux, and vector gen_sentence returned

Which one should I replace with list?

7-9 It's a difficult one as author said.I have no idea.

I hope you are not assuming we all own this book and have it at our
desk. Perhaps you should give more information if you desire
responses. I have no idea what 7-5, 7-5, and 7-9 are or say.

 

[Lambda]

7-4 The input file is a novel. There are more than 4, 000 'the' in the
text.
Breaking up the output will help? How to break up the output? Add
newlines?

7-5 Why use list? I can't see any benefit. List does not support
random accesses.
And there are several vectors:

Rule, Rule_collection, vector contains words the input split into,
vector populated by gen_aux, and vector gen_sentence returned

Which one should I replace with list?

7-9 It's a difficult one as author said.I have no idea.

7-4 The output produce 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.

Original code:

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

#include "split.h"

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

// find all the lines that refer to each word in the input
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;

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

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

 

[Lambda]

7-4 The input file is a novel. There are more than 4, 000 'the' in the
text.
Breaking up the output will help? How to break up the output? Add
newlines?

7-5 Why use list? I can't see any benefit. List does not support
random accesses.
And there are several vectors:

Rule, Rule_collection, vector contains words the input split into,
vector populated by gen_aux, and vector gen_sentence returned

Which one should I replace with list?

7-9 It's a difficult one as author said.I have no idea.

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

Original code:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>
#include <vector>

#include "split.h"
#include <time.h>

using std::istream; using std::cin;
using std::copy; using std::cout;
using std::endl; using std::find;
using std::getline; using std::logic_error;
using std::map; using std::string;
using std::vector; using std::domain_error;
using std::rand;

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

// read a grammar from a given input stream
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;
}

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

int nrand(int);

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

bool bracketed(const string& s)
{
return s.size() > 1 && s[0] == '<' && s[s.size() - 1] == '>';
}

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

int main()
{
// generate the sentence
vector<string> sentence = gen_sentence(read_grammar(cin));

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

// return a random integer in the range `[0,' `n)'
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;
}

It will read following rule to generate sentence:

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

 

[Lambda]

7-4 The input file is a novel. There are more than 4, 000 'the' in the
text.
Breaking up the output will help? How to break up the output? Add
newlines?

7-5 Why use list? I can't see any benefit. List does not support
random accesses.
And there are several vectors:

Rule, Rule_collection, vector contains words the input split into,
vector populated by gen_aux, and vector gen_sentence returned

Which one should I replace with list?

7-9 It's a difficult one as author said.I have no idea.

7-9 The implementation of nrand will not work for arguments greater
then RAND_MAX. Usually, this restriction is no problem, because
RAND_MAX is often the largest possible integer anyway, Nevertheless,
there are implementations under which RAND_MAX is much smaller than
the largest possible integer. For example, it is not uncommon for
RAND_MAX to be 32767 and the largest possible integer to be 2^31 - 1.
Reimplement nrand so that it works well for all values of n.

Original code:

// return a random integer in the range `[0,' `n)'
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;
}