栈的应用——编写简单计算器

数据结构实验报告

一、实验目的和要求

栈的应用

实现简易计算器

二、实验环境

软件环境：Vs2017 + devc++

硬件环境：①CPU：Intel（R）Core（TM）i7-8565U CPU
@1.80Ghz

      ②内存：16.0GB  

三、实验内容

任务：利用栈编写十进制整数的简易计算器【只包括±*/()这五个符号】

四、实验过程

用文字、图（流程图等）、表格等方式记录实验过程中分析、设计工作。

首先确定输入的内容储存方式，这里我打算采取string来储存输入

确定完输入内容的储存方式后，接下来要考虑的问题是如何利用栈来进行操作。

在这里我回顾了一下栈的运算：包括了初始化、析构、判满、判空、入栈、出栈、取栈顶元素，并且栈是一个先进后出的逻辑结构。

在确定了栈的运算后，我们可以建立两个栈，一个栈负责储存输入内容中的数字，另一个栈负责储存输入内容中的符号。

4.1 任务定义和问题分析

任务定义：掌握栈的应用技巧。

问题一：

   我们知道，运算是有优先级的，而优先级是由符号决定的，所以在进行栈运算之

前，我们需要对符号区分优先级，在这里我确实考虑了好多天，自己想的时候用if else罗列了24种（并没有罗列完全）情况，导致之后的运算过于繁琐，程序从未成功过。之后我咨询了我的同学，在他的帮助下，我才想起用switch case语句来进行操作。所以可以将‘#’ ‘+’ ‘-’ ‘*’ ‘/’ ‘(’ ‘)’分别罗列等级。

    问题二：解决了符号优先级的分类，再需要解决的就是当扫描到的符号与符号栈栈顶优先级的关系，在老师的讲课中我知道了老师将其分为四种情况【在接下来我用x1表示栈顶符号，用x2表示扫描到的符号】

①
x1 > x2 时：这时需要将数字栈顶的两个元素取出，然后根据当前符号栈顶的元素进行计算，再将计算好的数字入栈。然后符号栈栈顶元素出栈，扫描到的符号入栈；

②
X1<x2时：扫描到的符号直接入栈；

③
X1 = x2时：同x1 > x2，遵循左操作优先的原则

④
Eeror：终止运行

问题三：我们输入内容的存储方式是用string来存储的，那么12就变成了‘1’和‘2’，现在需要把输入的数字字符变成整数，就需要记录每个符号字符前的字符数【这里记录的字符数就是数字的位数】，然后再将数字字符转换成整数。

4.2 数据结构的选择和概要设计

数据结构：

存储结构：数组

逻辑结构：栈

概要设计：

建立两个栈分别存储数字和字符，通过比较运算来达到目的。

4.3 详细设计

在确定了栈的运算后，我们可以建立两个栈，一个栈负责储存输入内容中的数字，另一个栈负责储存输入内容中的符号。

进行栈运算之前，我们需要对符号区分优先级

解决的就是当扫描到的符号与符号栈栈顶优先级的关系

将数字字符转换成整数

输出结果

五、测试及结果分析

对各种数据运行程序和算法的结果记录和分析，并对错误所作的修改和结果。

①一开始我用的if else，结果并不如人意，并且没有好好地理解这个题的意思【因为一开始我把栈写的非常满，用同学的话来说这个栈只能解决这一个问题，太过单一化，所以他建议我从另一个角度思考】

②当我用了同学给的思路后，我的输出仍有问题，回顾主函数发现并未出现问题，所以我在栈的实现中寻找bug，最后发现在gettop()函数中，函数的返回并不是【head-1】，而是返回【head】，所以造成了一个漏洞

{这里说明一下：每次入栈一个元素后，head都会进行++操作，所以导致head位置上的数组位依然没有确定的数，导致该函数返回的是一个随机数}

5.1 实验数据

用于测试算法和程序的测试数据。

5.2 结果及分析

记录测试结果，实验中遇到的问题和相对应的解决办法，对主要算法的时间和空间等性能的分析结果。要求附上运行界面截图。

 时间：出栈入栈是O(1)，然后主函数有个扫描输入内容是O(n)；

 空间：使用的float和char，暂时不会算

六、实验收获

完成实验后的收获、总结、心得

哎呦我去终于知道栈是什么玩意儿了，刚开课的时候老师一直在讲栈的概念这个那个，我都听懂了，但让我去应用我一窍不通，在经历了心态崩溃恢复崩溃恢复的一周后，我终于明白栈到底是个什么东西了，实验中确实有了很多收获，例如加深了对栈的写法的印象，了解了栈可以在什么情况下使用（只是了解了一部分，还需要多阅读别的东西），复习了怎么把数字字符变成数字……

七、（源代码）

这一部分是栈的声明和实现

这一部分是栈的实现和函数的实现
这一部分是主函数的实现。