7-0-2.cpp

Accelerated C++ 课后练习题 本人自己完成、可供参考

#include<iostream>
#include<map>
#include<vector>
#include<string>
using namespace std;

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

vector<string> split(const string& s)
{
	vector<string> ret;
	typedef string::size_type string_size;
	string_size i=0;

	//ivarinant: we have processed characters [original value of i, i)
	while(i!=s.size())
	{
		//ignore leading blanks
		//invariant: characters in range [original i, current i) are all spaces
		while(i!=s.size()&&isspace(s[i]))
			++i;
		//find end of next word
		string_size j=i;
		//invariant: none of the characters in range [original j,current j)is a space
		while(j!=s.size()&&!isspace(s[j]))
			j++;
		//if we found some nonwhitespace characters
		if(i!=j)
		{
			//copy from s starting at i and taking j-i chars
			ret.push_back(s.substr(i,j-i));
			i=j;
		}
	}
	return ret;
}



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

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

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


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

//read a grammar from a given input stream
Grammar read_grammar(istream& in)
{
	Grammar ret;
	string line;

	//read the input
	while(getline(in,line))
	{
		if(line=="exit")
			break;
		//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;
}





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



#ifdef PRIMER
Grammar read_grammar()
{
	vector<string> inputdata;
	inputdata.push_back("<noun> cat");
	inputdata.push_back("<noun> dog");
	inputdata.push_back("<noun> table");
	inputdata.push_back("<noun-phrase> <noun>");
	inputdata.push_back("<noun-phrase> <adjective> <noun-phrase>");
	inputdata.push_back("<adjective> large");
	inputdata.push_back("<adjective> brown");
	inputdata.push_back("<adjective> absurd");
	inputdata.push_back("<verb> jumps");
	inputdata.push_back("<verb> sits");
	inputdata.push_back("<location> on the stairs");
	inputdata.push_back("<location> under the sky");
	inputdata.push_back("<location> wherever it wants");
	inputdata.push_back("<sentence> the <noun-phrase> <verb> <location>");
	Grammar ret;
	for(vector<string>::iterator it=inputdata.begin();it!=inputdata.end();++it)
	{
		//split the input into words 
		vector<string> entry=split(*it);
		if(!entry.empty())
		//use the category to store the associated rule
		ret[entry[0]].push_back(Rule(entry.begin()+1,entry.end()));
	}
	return ret;
}

int main()
{
	//generate the sentence 
	vector<string> sentence=gen_sentence(read_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;
}

#endif