根据文法随机生成句子

sentence.cpp

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <cassert>
#include <cstdlib>

using namespace std;

typedef vector<string> rule;
typedef vector<rule> ruleseq;
typedef map<string, ruleseq> grammer;

vector<string> split(const string &s)
{
    vector<string> v;
    istringstream iss(s);
    copy(istream_iterator<string>(iss), istream_iterator<string>(), back_inserter(v));
    return v;
}

grammer read_grammer(istream &is)
{
    grammer gram;
    string line;
    while (getline(is, line))
    {
        vector<string> entry = split(line);
        if (!entry.empty())
        {
            gram[entry[0]].push_back(rule(entry.begin() + 1, entry.end()));
        }
    }
    return gram;
}

bool bracketed(const string &s)
{
    return s.size() > 1 && s.front() == '<' && s.back() == '>';
}

int nrand(int n)
{
    return rand() % n;
}

vector<string> make_sentence_aux(const grammer &gram, const string &word)
{
    if (!bracketed(word))
    {
        return vector<string>(1, word);
    }
    grammer::const_iterator i = gram.find(word);
    assert(i != gram.end());
    const ruleseq &rules = i->second;
    const rule &r = rules[nrand(rules.size())];
    vector<string> words;
    for (auto i = r.begin(); i != r.end(); ++i)
    {
        auto ret = make_sentence_aux(gram, *i);
        copy(ret.begin(), ret.end(), back_inserter(words));
    }
    return words;
}

vector<string> make_sentence(const grammer &gram)
{
    return make_sentence_aux(gram, "<sentence>");
}

int main()
{
    ifstream ifs("in.txt");
    auto gram = read_grammer(ifs);
    auto sentence = make_sentence(gram);
    copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
    cout << endl;
}