实验二 栈

实验二 栈

实验目的和要求

  1. 理解栈的特点
  2. 掌握栈这种结构的算法设计
  3. 学会运用栈来储存数据和求解相关问题

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 设计出一个模板栈,测试栈的各种运算
  2. 利用模板栈实现一个计算器来计算给定表达式的值

实验过程

任务一

设计

根据栈的特点,栈应具有以下属性和功能:

属性:

  • 栈的最大容量
  • 栈顶的指针
  • 栈中元素的数量

功能:

  • 入栈(压栈)
  • 出栈(弹栈)
  • 获取栈顶元素
  • 判断栈是否为空或是否已满

本次实验采用 C++ 作为编程语言,可用 C++ 中的模板类来封装栈,以实现储存不同类型的数据。

编码实现

通过 C++ 的模板知识来编写模板类的代码。

测试

测试栈结果

任务二

设计

想要计算一个表达式,第一步应该是录入需要的表达式。将表达式录入后,可以将表达式储存在 string 中。对于输入的表达式,考虑到不同的用户的习惯,表达式中是否存在空格是不能确定的,而且用户输入的表达式是否合法也不确定,因此在计算前应将表达式格式化并进行检验,若表达式不合法,应提示用户重新输入。

获取到表达式后,将运算符与运算数分离开,分别储存在两个栈中。对于如何进行计算,若使用优先级的方法,则对应关系将会很复杂,可以换个角度进行思考。

本次实验中只用到了六种运算符(+、-、*、/、(、))。在扫描格式化后的表达式时,进行以下讨论:

  1. 先考虑 “(“,若遇到此运算符,应直接压入栈中继续扫描表达式
  2. 若遇到 “)”,那么应该将运算符栈中的运算符依次取出进行计算,直到栈顶运算符为 “(“,将 “(“ 弹出并继续扫描表达式
  3. 如果是 “+” 或 “-“,那么应考虑栈顶的运算符,如果栈顶运算符为 “(“ 则应该将扫描到的运算符压入栈,如果栈顶运算符为 “+”、”-“、”*”、”/“则应该将栈顶运算符取出并进行计算
  4. 如果扫描到的运算符为 ““ 或 “/“,那么应考虑栈顶的运算符,如果栈顶运算符为 “(“、”+”、”-“ 则应该将扫描到的运算符压入栈,如果遇到 ““、”/“ 则应该将栈顶运算符取出并进行计算
    至此,所有的可能都被讨论完毕。
    用户输入的表达式中可能含有除法运算,受到 C++ 中的整数除法运算限制,其结果只能为整数,这样会导致计算的结果出错。对此,可以设计一个 Rational 类(有理数类),将用户输入的表达式中的数字使用自己编写的 stringToRational 函数来转换为 Rational 对象,同时重载 Rational 类的 +、-、*、/ 运算符,这样就能将结果保留为分数形式或带有小数点的形式。

编码实现

通过已有的模板栈和以上设计思路进行编写代码。

测试

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

测试计算器结果

实验收获

通过本次实验,掌握了栈的设计方法,体会到了栈的先进后出的特点。利用这一特点实现了简单的计算器。实际上,在解决实际问题时,若某种现象满足先进后出的规律,都可以考虑到使用栈来作为管理数据的方式,在本次实验中,计算表达式时,从左向右扫描表达式根据后面的操作符来计算操作数,未计算的操作数将被放在一边等待计算,明显符合栈的特点,故可以采用栈来解决问题。

在设计计算的方式时,可以从不同的角度来考虑计算的先后顺序,换一种方式,则可能会简化问题。