文本单词查询复合表达式求值的实现案例分析

这篇具有很好参考价值的文章主要介绍了文本单词查询复合表达式求值的实现案例分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        本文讨论的“文本单词查询复合表达式求值的实现”案例,来自C++ primer第四版,该案例面向对象编程和泛型编程,涉及类的继承、抽象、多态、句柄、标准IO库、容器、算法库,是综合性很强的程序

        该程序实现文本中查找单个单词,“非”查询(使用~操作符),“或”查询(使用|操作符),“与”查询(使用&操作符),组合查询(如fiery & bird | wind),查询表达式求值 并 打印输出查询结果:符合查询条件的文本共多少行、在查询本文的第几行、以及文本内容,查询使用文本如下:

Alice Emma has long flowing red hair. 
Her Daddy says when the wind blows 
through her hair, it looks almost alive, 
like a fiery bird in flight. 
A beautiful fiery bird, he tells her, 
magical but untamed. 
"Daddy, shush, there is no such thing," 
she tells him, at the same time wanting 
him to tell her more.
Shyly, she asks, "I mean, Daddy, is there?"   

       一、程序架构

        创建标准IO库的ifstream对象infile,定义的辅助函数openfile在命令行模式下,用对象infile打开文本文件,具体操作是:在命令行下输入程序名字及文本文件所在目录

        TextQuery类实现文本的读取存储,容器vector按行存储文本,容器map存储所有单词所在的行的set容器,接口函数run_query返回一个单词所在的行的set容器,text_line返回具体行的文本,size返回存储的文本共多少行

        句柄类Query,包装类型为查询基类Query_base的模板句柄Handle实例对象h,该句柄实例包装查询基类指针,Query类对象由查询基类指针构造 或 string字符串(由字符串构造的对象返回的是基类指针)构造,Query类对象的构造,最终初始化查询基类指针注意:查询基类指针指向具体的查询对象:继承自查询基类Query_base的子类WordQuery、NotQuery、BinaryQuery(BinaryQuery的子类AndQuery、OrQuery)的对象

        句柄类的友元函数,是重载 |、&、~操作符的函数,返回句柄类对象(动态构造的具体查询对象返回的是查询基类指针,查询基类指针可以隐式转换为句柄类对象),用以实现查询表达式

        句柄类Query的接口函数display显式具体查询表达式,接口函数eval返回符合查询条件的set容器(存储所有符合查询条件的文本行号)

        程序几个版本的演变及完整代码,请点击这里(本文讨论的是第六版)

       主函数代码:

int main(int argc, char**argv )
{
    std::ifstream infile;
    if(argc<2 ||!open_file(infile,argv[1] ) ) {
        std::cerr << "No input file!" << std::endl;
        return EXIT_FAILURE;
    }
    TextQuery tq;
    tq.read_file(infile );
    
    Query q = Query("fiery") & Query("bird") | Query("wind");
    std::set<TextQuery::line_no> qset = q.eval(tq );
    q.display(std::cout ); // ((fiery & bird) | wind)
    print_results(qset,"",tq );
          
    return 0;
}

        Query q = Query("fiery") & Query("bird") | Query("wind");  Query对象q的构造过程:字符串"fiery"构造Query临时对象(包含查询基类Query_base的子类WordQuery类的对象),字符串"bird"构造Query临时对象(包含查询基类Query_base的子类WordQuery类的对象),Query类的友元函数重载 & 操作符,构造左操作数Query("fiery"),右操作数Query("bird")的Query临时对象(包含查询基类Query_base的子类BinaryQuery类的子类AndQuery类的对象),Query类的友元函数重载 | 操作符,构造左操作数为Query临时对象(包含查询基类Query_base的子类BinaryQuery类的子类AndQuery类的对象),右操作数Query("wind")的Query临时对象(包含查询基类Query_base的子类BinaryQuery类的子类OrQuery类的对象),表达式求值的Query临时对象复制构造Query类对象q

        std::set<TextQuery::line_no> qset = q.eval(tq );Query类对象q,调用eval函数,把存储文本的TextQuery类对象的引用传递到函数,实现表达式查询Query类对象q包含的Handle句柄对象(包含查询基类Query_base指针),利用重载的操作符-> 以及利用查询类的多态性将函数调用分发到基类Query_base指针指向的各个具体的派生类的eval函数,最终返回符合条件的set容器

UML类设计图   文本单词查询复合表达式求值的实现案例分析,C++,c++,句柄

        二、查询基类Query_base及其子类WordQuery、NotQuery、BinaryQuery(BinaryQuery的子类AndQuery、OrQuery)

        查询基类Query_base代码:

class Query_base{
    friend class Query; //句柄Query
    friend class Handle<Query_base >;//类型为Query_base的句柄模板实例
protected://派生类访问
    typedef TextQuery::line_no line_no;
    virtual ~Query_base() {  }
private:   //两个接口,用户和Query_base类的派生类只通过句柄Query使用Query_base类
    virtual std::set<line_no> eval(const TextQuery&) const = 0;
    virtual std::ostream& display(std::ostream& = std::cout) const = 0;
};

        查询基类Query_base的子类WordQuery类的代码:

class WordQuery: public Query_base{
    friend class Query;//句柄Query友元//调用构造函数需要
    WordQuery(const std::string &s ):query_word(s ) {  }
    std::set<line_no > eval(const TextQuery &t)const{  //实现基类纯虚函数eval
        return t.run_query(query_word ); //用到了TextQuery类的成员函数run_query
    }
    std::ostream& display(std::ostream &os)const{      //实现基类纯虚函数display
        return os << query_word;
    }
    std::string query_word;  //数据成员query_word
};

        查询基类Query_base的子类NotQuery类的代码:

class NotQuery: public Query_base{
    friend Query operator~(const Query & );//调用构造函数需要
    NotQuery(Query q ):query(q ) {  } //构造
    std::set<line_no > eval(const TextQuery & )const;
    std::ostream& display(std::ostream &os )const{
        return os << "~(" << query << ")"; //输出操作符的使用最终是对Query_base对象的虚函数的调用
    }
    const Query query;  //数据成员Query句柄对象
};
std::set<TextQuery::line_no > NotQuery::eval(const TextQuery &file) const{
    std::set<TextQuery::line_no > has_val = query.eval(file );
    std::set<line_no > ret_lines;
    for(TextQuery::line_no n = 0; n != file.size(); ++n ){    
        if(has_val.find(n) == has_val.end() ) //没找到,就插入
            ret_lines.insert(n);
    }
    return ret_lines;
}    

        查询基类Query_base的子类BinaryQuery类的代码:

class BinaryQuery: public Query_base{
protected:
    BinaryQuery(Query left, Query right, std::string op ):lhs(left),rhs(right),oper(op) {  }
    std::ostream& display(std::ostream &os)const{
        return os << "(" << lhs << " " << oper << " "
                        << rhs << ")"; //输出操作符的使用最终是对Query_base对象的虚函数的调用
    }
    const Query lhs, rhs;
    const std::string oper;
};
 

        查询基类Query_base的子类BinaryQuery类的子类AndQuery类的代码:

class AndQuery: public BinaryQuery{
    friend Query operator&(const Query &, const Query & );//调用构造函数需要
    AndQuery(Query left, Query right ):BinaryQuery(left, right, "&" ) {  }
    std::set<line_no > eval(const TextQuery & )const;
};
std::set<TextQuery::line_no > AndQuery::eval(const TextQuery &file) const{
    std::set<line_no > left = lhs.eval(file ),
                    right = rhs.eval(file );
    std::set<line_no > ret_lines;
    set_intersection(left.begin(), left.end(),
                    right.begin(),right.end(),
                    inserter(ret_lines, ret_lines.begin()) );
    return ret_lines;
}

        算法std::set_intersection,构造一个排序范围,它是两个排序范围的集合交集,实现&运算

        查询基类Query_base的子类BinaryQuery类的子类OrQuery类的代码:

class OrQuery: public BinaryQuery{
    friend Query operator|(const Query &, const Query & );//调用构造函数需要
    OrQuery(Query left, Query right ):BinaryQuery(left, right, "|" ) {  }
    std::set<line_no > eval(const TextQuery & )const;
};
std::set<TextQuery::line_no > OrQuery::eval(const TextQuery &file) const{
    std::set<line_no > right = rhs.eval(file ),
                    ret_lines = lhs.eval(file );    //返回的set对象ret_lines初始化为lhs的结果
    ret_lines.insert(right.begin(), right.end() );
    return ret_lines;
}

        三、句柄模板

        句柄简单的来讲,它是一个类,包装了一种基类指针的一个类,该指针指向动态创建的有继承关系的对象,句柄确保指针指向的对象在有指针指向的时候不会释放,在没有指针指向的时候释放,句柄避免了对象的重复创建,句柄在C++沉思录一书中有详细的描述,可以点击这里查看

       本人认为,句柄,这个包含一个基类指针的类,真的是为实现面向对象编程的多态性而生,安全、方便,句柄对象的构造、复制、赋值、析构轻松、简单,当你真正理解本文论述的程序,你会发现,句柄是这个程序的灵魂

        句柄模板类Handle代码:文章来源地址https://www.toymoban.com/news/detail-816890.html

template<class T> class Handle{
private:
    T* ptr;          //指向基础对象的指针
    size_t *use;     //指针计数 //即多少个指针指向同一个基础对象
    void rem_ref(){  //删除基础对象(根据计数判断是否删除)
        if(--*use == 0){
            delete ptr; //删除基础对象
            delete use; //删除计数
        }
    }
public:
    Handle(T *p = 0 ):ptr(p ),use(new size_t(1) ){ } //指针ptr指向动态分配的基础对象的地址
    //复制控制
    Handle(const Handle& h):ptr(h.ptr ), use(h.use) { ++*use; } //复制,++*use
    Handle& operator=(const Handle& rhs );
    ~Handle() { rem_ref(); }   //Handle对象析构 // 删除基础对象(根据计数判断是否删除)
    //用于访问基础对象
    const T& operator*()const; //解引用操作符
    const T* operator->()const; //成员操作符            
};
 
template<class T>
inline Handle<T>& Handle<T>:: operator=(const Handle& rhs)
{
    ++*rhs.use;     //protect against self-assignment //防止自我复制
    rem_ref();    //decrement use count and delete pointers if needed
    ptr = rhs.ptr;
    use = rhs.use;
    
    return *this;
}
 
template<class T>//const Handle对象可以调用,返回类型是const T&不可以修改基础对象
inline const T& Handle<T>::operator*()const   
{
    if(ptr)
        return *ptr;
    throw std::runtime_error("dereference of unbound Handle");
}
 
template<class T>
inline  const T* Handle<T>::operator->()const
{
    if(ptr)
        return ptr;
    throw std::runtime_error("dereference of unbound Handle");
} 

        四、句柄类Query(包装句柄模板实例对象 Handle<Query_base > h)的代码

class Query{  //使用Query友元的类,增加句柄模板实例为友元
    friend Query operator~(const Query &);
    friend Query operator|(const Query &, const Query &);
    friend Query operator&(const Query &, const Query &);
public:
    Query(const std::string &); //!!!  
    std::set<TextQuery::line_no> eval(const TextQuery &t)const {return h->eval(t); } //!!!
    std::ostream &display(std::ostream &os = std::cout) const {return h->display(os); }//!!!
private:
    Query(Query_base *query):h(query) {  } //!!!操作符创建Query对象调用
    Handle<Query_base > h; //!!!
};
Query::Query(const std::string &s ):h(new WordQuery(s ) ) {   }    ; //!!!创建WordQuery对象
inline std::ostream& operator << (std::ostream &os, const Query &q){
    return q.display(os ); //参数q是const,调用的display函数也必须是const
}

//return语句隐式调用接受Query_base指针的Query构造函数//隐式类型转换
inline Query operator&(const Query &lhs, const Query &rhs){
    return new AndQuery(lhs, rhs );
}
inline Query operator|(const Query &lhs, const Query &rhs){
    return new OrQuery(lhs, rhs );
}
inline Query operator~(const Query &oper){
    return new NotQuery(oper );
}      

        五、查询结果打印函数

void print_results(const std::set<TextQuery::line_no > &locs, 
                   const std::string &sought,
                   const TextQuery &file  )
{
    typedef std::set<TextQuery::line_no > line_nums;
    line_nums::size_type size = locs.size();
    std::cout << "\n" << sought << " occurs "
            << size << " "
            << make_plural(size, "time", "s" ) << std::endl;
    line_nums::const_iterator it = locs.begin();
    for( ; it != locs.end(); ++it ){
        std::cout << "\t(line "
            << (*it) + 1 << ")"
            << file.text_line(*it ) << std::endl;
    }
}
 
std::string make_plural(std::size_t ctr, 
                            const std::string &word,
                            const std::string &ending )    //make_plural //单词复数形式
{
    return (ctr == 1 ) ? word : word + ending;
}

        六、文件打开函数open_file

std::ifstream& open_file(std::ifstream &in, const std::string &file )
{
    in.close(); //如果已经打开
    in.clear();
    in.open(file.c_str() ); //打开文件
    return in;
}

        七、文本存储TextQuery类

class TextQuery{
public:
    typedef std::vector<std::string>::size_type line_no;
    void read_file(std::ifstream &is){  //std::ifstream &
        store_file(is);
        build_map();
    }
    std::set<line_no> run_query(const std::string & )const;
    std::string text_line(line_no )const;
    line_no size() const{ return lines_of_text.size(); } //!!!const函数
private:
    void store_file(std::ifstream & );  //std::ifstream & //保存文件
    void build_map();                   //从文件提取单词(去除标点符号)并记录单词所在文件的行号   
    std::vector<std::string> lines_of_text;  
    std::map< std::string, std::set<line_no> > word_map;//
};
 
void TextQuery::store_file(std::ifstream &is )
{
    std::string textline;
    while(getline(is,textline) ){
        lines_of_text.push_back(textline );
    }
}
 
void TextQuery::build_map()
{
    for( line_no line_num = 0; 
         line_num != lines_of_text.size();
         ++line_num )
    {
        std::istringstream line(lines_of_text[line_num] );//从std::vector读到 std::istringstream
        std::string word;        
        while(line >> word ){
            word.std::string::erase( std::remove_if(word.begin(),word.end(), static_cast<int(*)(int) >(&ispunct)), word.end() );//!!!去除标点符号
            word_map[word].insert(line_num );
        }
    }    
}
 
std::set<TextQuery::line_no> TextQuery::run_query(const std::string &query_word )const
{
    std::map<std::string,std::set<line_no> > ::const_iterator loc = word_map.find(query_word ); //std::map里查找行std::set
    if(loc == word_map.end() )
        return std::set<line_no>();  //没找到返回set空对象
    else
        return loc->second;
}
 
std::string TextQuery::text_line(line_no line ) const
{
    if(line <lines_of_text.size() )
        return lines_of_text[line ];
    throw std::out_of_range("line number out of range");
}

到了这里,关于文本单词查询复合表达式求值的实现案例分析的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之表达式求值

     前言 运用堆栈解决表达式的求值,代码思路为: 1.定义两个栈,一个char类型的栈用于存放运算符(ysf)一个int类型的栈用于存放操作数(czs) 如一个表达式3+6*9,将“+”,“*”入ysf栈,将“3”“6”“9”入czs栈 2.运用getchar进行数据的录入,如果接收的是运算符,将其插入到运

    2024年04月29日
    浏览(34)
  • 中缀表达式求值(栈的应用)

    AcWing算法基础课-3302.表达式求值 给定一个表达式,其中运算符仅包含 +,-,*,/ (加 减 乘 整除),可能包含括号,请你求出表达式的最终值。 注意: 数据保证给定的表达式合法。 题目保证符号 - 只作为减号出现,不会作为负号出现,例如, -1+2 , (2+2)*(-(1+1)+2) 之类表达式均不

    2024年02月05日
    浏览(53)
  • 数据结构 实验2——表达式求值

    一、实验名称:表达式求值 二、实验学时: 6 学时 三、实验目的 1.理解栈的结构特点和基本操作特性; 2.掌握利用栈实现表达式求值算法。 四、实验内容 ( 步骤 ) 输入一个算术表达式(以“=”结束),求其值。要求表达式以“=”结束,操作数为多位实数,对错误表达式要进行

    2023年04月08日
    浏览(38)
  • 【数据结构】12 堆栈应用:表达式求值

    有一个常量表达式的中缀表达式为:5 + 6 / 2 - 3 * 4,其后缀形式表示为: 5 6 2 / + 3 4 × -。后缀表达式的特点是运算符位于两个预算数之后。其前缀表达式为: - + 5 / 6 2 × 3 4。 后缀表达式相比于中缀表达式的求值要容易很多。 从左到右扫描该表达式: (1)遇见运算数5 6 2时不

    2024年02月20日
    浏览(53)
  • 【表达式求值】整型提升和算术转换

    目录 1. 整型提升 1.1整型提升的意义: 1.2如何进行整体提升呢? 2. 算术转换 3. 问题表达式解析 3.1 表达式1 3.2 表达式2 3.3 表达式3 3.4 表达式4 4. 操作符属性 ​ 总结: C语言中 整型算术运算 总是至少以整型类型的精度来进行的。 为了获得这个精度,表达式中的 字符和短整型

    2024年02月21日
    浏览(36)
  • 数据结构 | 栈的中缀表达式求值

    目录 什么是栈? 栈的基本操作 入栈操作 出栈操作 取栈顶元素 中缀表达式求值 实现思路 具体代码 栈是一种线性数据结构,具有“先进后出”(Last In First Out, LIFO)的特点。它可以看作是一种受限的线性表,只能在表的一端进行插入和删除操作,这一端被称为栈顶,另一端

    2024年02月02日
    浏览(54)
  • LeetCode:150. 逆波兰表达式求值—栈

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 来源:力扣(LeetCode) 难度: 简单 提示:

    2023年04月16日
    浏览(55)
  • 『力扣刷题本』:逆波兰表达式求值

    大家好久不昂,最近 1 个多月罗根一直在备考期末,文章发的很少。 现在已经放寒假啦,学习自然也不能拉下,毕竟 4 月份就要去参加蓝桥杯了。 先给自己定个小目标,日更 2 篇! 咳咳,下面马上开始讲题👇 给你一个字符串数组  tokens  ,表示一个根据 逆波兰表示法 表

    2024年01月16日
    浏览(38)
  • JAVA练习99-逆波兰表达式求值

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、题目-逆波兰表达式求值 1.题目描述 2.思路与代码 2.1 思路 2.2 代码 总结 提示:这里可以添加本文要记录的大概内容: 4月5日练习内容 提示:以下是本篇文章正文内容,下面案例可供参考

    2023年04月08日
    浏览(44)
  • 《C和指针》笔记21:表达式求值

    C的整型算术运算总是至少以 缺省整型类型的精度 来进行的。为了获得这个精度,表达式中的 字符型和短整型操作数在使用之前被转换为普通整型,这种转换称为整型提升(integral Promotion) 。例如,在下面表达式的求值中, b和c的值被提升为普通整型,然后再执行加法运算

    2024年02月09日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包