C++ Primer 中的textquery例子

要求

1. 从文本读取数据并构建查询表
2. 返回查询结果
3. 分析查询操作
4. 支持操作与或非运算

interface

1. TextQuery
2. QueryResult
3. Query: 保存需要的执行的操作
   1. 支持从字符串建立单词查询
   2. 支持 & | ~ 操作符

实现

TextQuery 和 QueryResult

查询结果需要输出行号和该行内容. 可以建立单词与行号集合的查询表.

std::map<std::string, std::set<line_no>> searchTable;

使用vector保存每行内容.
因为这些内容在查询结果中也要使用, 可以使用智能指针方便内容共享
结果中需要有行号集合的指针. 为了输出需要每行内容的指针

// 声明文件
 class QueryResult;
class TextQuery{
    using line_no = std::vector<std::string>::size_type;
public:
    TextQuery() = default;
    TextQuery(std::ifstream&);
    QueryResult query(const std::string&) const;
private:
    std::shared_ptr<std::vector<std::string>> textContent;
    std::map<std::string, std::shared_ptr<std::set<line_no>>> searchTable;
};

class QueryResult{
public:
    using line_no = TextQuery::line_no;
    using iterator = std::set<line_no>::iterator;
    QueryResult(const std::string& _query, 
                std::shared_ptr<std::vector<std::string>> _content, 
                std::shared_ptr<std::set<line_no>> _result = std::make_shared<std::set<line_no>>())
        : query(_query)
        , content(_content)
        , result(_result)
        {}
    std::set<line_no>::iterator begin() { return result->begin(); }
    std::set<line_no>::iterator end() { return result->end(); }
    std::shared_ptr<std::vector<std::string>> get_content(){return content;}
    friend std::ostream& operator<<(std::ostream&, const QueryResult&);
private:
    const std::string query;
    std::shared_ptr<std::vector<std::string>> content;
    std::shared_ptr<std::set<line_no>> result;
};

函数实现

TextQuery::TextQuery(istream& in)
{
    string line;
    while (getline(in, line))
    {
        textContent->emplace_back(line);
        istringstream ss(line);
        string word;
        line_no n = textContent->size() - 1;
        while (ss >> word)
        {
            auto p = searchTable[word];
            if (!p) p.reset(new set<line_no>);
            p->insert(n);
        }
    }
}

QueryResult TextQuery::query(const string& sought) const
{
    auto res = searchTable.find(sought);
    if (res == searchTable.end()) return QueryResult(sought, textContent);
    return QueryResult(sought, textContent, res->second);
}
ostream& operator<<(ostream& os, const QueryResult& res)
{
    os << res.query << " occurs " << res.result->size() << (res.result->size() > 1 ? "times" : "time") << endl;
    for (auto l : *res.result) os << "\t(line " << l + 1 << (*res.content)[l] << ")" << endl;
    return os;
}

Query

因为要支持与, 或, 非(&, |, ~)运算. 每种查询执行的操作不同, 定义一个抽象基类. 有两个纯虚函数 rep() 返回该查询操作的字符串描述. eval() 执行查询

derived.png

QueryBase

class QueryBase{
    friend class Query;
protected:
     virtual ~QueryBase() = default;

private:
    virtual QueryResult eval(const TextQuery&) const = 0;
    virtual std::string rep() const = 0;
};

// Query

class Query{
    friend Query operator&(const Query&, const Query&);
    friend Query operator|(const Query&, const Query&);
    friend Query operator~(const Query&);
public:
    Query(const std::string&);
    QueryResult eval(const TextQuery& t){return q->eval(t);}
    std::string rep(){return q->rep();}
private:
    std::shared_ptr<QueryBase> q;
    Query(std::shared_ptr<QueryBase> _q):q(_q){}
};

WordQuery

class WordQuery:public QueryBase{
    friend class Query;
    WordQuery(const std::string& s):word(s){}
    QueryResult eval(const TextQuery& t) { return t.query(word);}
    std::string rep() {return word;}
    std::string word;
};

Query::Query(const string& w):q(new WordQuery(w)){}

NotQuery 和 ~操作

class NotQuery : public QueryBase {
    friend Query operator~(const Query&);
    NotQuery(const Query& q) : query(q) {}
    QueryResult eval(const TextQuery&) const;
    std::string rep() const
    {
        return "~(" + query.rep() + ")";
    }
    Query query;
};


inline Query operator&(const Query&lhs, const Query& rhs)
{
    return shared_ptr<QueryBase>(new AndQuery(lhs, rhs));
}

BinartQuery

class BinaryQuery : public QueryBase {
protected:
    BinaryQuery(const Query& _lhs, const Query& _rhs, std::string _op) : lhs(_lhs), rhs(_rhs), op(_op) {}
    std::string rep() const override
    {
        return "(" + lhs.rep() + " " + op + " " + rhs.rep() + ")";
    }
    Query lhs, rhs;
    std::string op;
};

AndQuery 和 OrQuery

class AndQuery : public BinaryQuery {
    friend Query operator&(const Query& lhs, const Query& rhs);
    AndQuery(const Query& lhs, const Query& rhs) : BinaryQuery(lhs, rhs, "&") {}
    QueryResult eval(const TextQuery&) const;
};

class OrQuery : public BinaryQuery {
    friend Query operator|(const Query& lhs, const Query& rhs);
    OrQuery(const Query& lhs, const Query& rhs) : BinaryQuery(lhs, rhs, "|") {}
    QueryResult eval(const TextQuery&) const;
};


inline Query operator&(const Query&lhs, const Query& rhs)
{
    return shared_ptr<QueryBase>(new AndQuery(lhs, rhs));
}
inline Query operator|(const Query&lhs, const Query& rhs)
{
    return shared_ptr<QueryBase>(new OrQuery(lhs, rhs));
}

核心 eval 实现

QueryResult OrQuery::eval(const TextQuery& t) const
{
    auto left  = lhs.eval(t);
    auto right = rhs.eval(t);
    auto res   = make_shared<set<line_no>>(left.begin(), left.end());
    res->insert(right.begin(), right.end());
    return QueryResult(rep(), left.get_content(), res);
}

QueryResult AndQuery::eval(const TextQuery& t) const
{
    auto left  = lhs.eval(t);
    auto right = rhs.eval(t);
    auto res   = make_shared<set<line_no>>();
    set_intersection(left.begin(), left.end(), right.begin(), right.end(), inserter(*res, res->begin()));
    return QueryResult(rep(), left.get_content(), res);
}


QueryResult OrQuery::eval(const TextQuery& t) const
{
    auto left  = lhs.eval(t);
    auto right = rhs.eval(t);
    auto res   = make_shared<set<line_no>>(left.begin(), left.end());
    res->insert(right.begin(), right.end());
    return QueryResult(rep(), left.get_content(), res);
}

QueryResult AndQuery::eval(const TextQuery& t) const
{
    auto left  = lhs.eval(t);
    auto right = rhs.eval(t);
    auto res   = make_shared<set<line_no>>();
    set_intersection(left.begin(), left.end(), right.begin(), right.end(), inserter(*res, res->begin()));
    return QueryResult(rep(), left.get_content(), res);
}

命令分析

为了简便有一些限制

1. 不能有空格
2. 没有转义字符. 无法搜索包含 &|~的单词
3. 表达式错误, 程序会崩溃.

Query parseQuery(const string& com)
{
    static map<char, int> opPriority{{')', 0}, {'|', 1}, {'&', 2}, {'~', 3}, {'(', 4}};
    stack<char> stOp;
    stack<Query> stQuery;
    string::const_iterator cur = com.begin();
    string::const_iterator end = com.end();
    while (cur != end)
    {
        if (opPriority.count(*cur))
        {
            while (!stOp.empty() && opPriority[*cur] <= opPriority[stOp.top()])
            {
                char op = stOp.top();
                stOp.pop();
                switch (op)
                {
                case '~': {
                    Query q = stQuery.top();
                    stQuery.pop();
                    stQuery.push(~q);
                    break;
                }
                case '&': {
                    Query r = stQuery.top();
                    stQuery.pop();
                    Query l = stQuery.top();
                    stQuery.pop();
                    stQuery.push(l & r);
                    break;
                }
                case '|': {
                    Query r = stQuery.top();
                    stQuery.pop();
                    Query l = stQuery.top();
                    stQuery.pop();
                    stQuery.push(l | r);
                }
                default: break;
                }
            }
            if (*cur == '(')
                stOp.push(')');
            else if (*cur != ')')
                stOp.push(*cur);
            ++cur;
        }
        else
        {
            string::const_iterator temp = cur;
            while (cur != end && !opPriority.count(*cur)) ++cur;
            stQuery.emplace(string(temp, cur));
        }
    }
    return stQuery.top();
}