HUNAN UNIVERSITY
课程实验报告
题目：四则运算表达式求值
学生姓名：
如何申请qq号学生学号：
专业班级：
指导老师：
完成日期：
一．需求分析
1.输入形式
用户需输入一个中缀表达式，用户需输入四则运算符.括号和数字回车表示结束才，如：（3+4）*5/3。当用户输入错误的符号时，提示用户输入有误，并重新输入。具体格式：
请输入四则运算表达式：
2.输出形式
如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和计算结果，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。具体格式：
后序表达式为：
最终结果为：
3.程序功能
该程序可以将用户输入的中缀表达式转换为后缀表达式并计算其结果
4.测试数据
1.请输入四则运算表达式：
21+23*（12-6）
后缀表达式为：
21 23 12 6 -*+
计算结果是 小年祝福语大全 159
2.请输入四则运算表达式：
4/5+4-5
后缀表达式为：
4 5 / 4 + 5 -
计算结果是 -0.2
3.请输入四则运算表达式：
1.5+4/5
输入有误，请重新输入
4.请输入四则元素表达式：
21^7%y*4
输入有误，请重新输入
5.请输入四则运算表达式：
EXIT
程序结束运行
二．概要设计
1.抽象数据类型
定义一个二叉树，用来存储用户输入的表达式。表达式通过定义一个栈来计算。
1为了访问二叉树中各节点的值，定义一个二叉树节点类，其ADT设计如下：
数据对象：用户输入的中缀表达式
数据关系：二叉树所对应的数据关系
基本操作：
int val() ; //返回结点的数值
void setLeft(Node* ) ; //设置左结点
void setRight(Node* ); //设置右结点
Node* left()const; //返回左结点
Node* right()const ;//返回右结点
③为了更快对二叉树中的元素进行插入和查操作，使用二叉链表实现二叉树
4为了计算中缀表达式的值，通过定义一个栈来计算。栈的ADT设计如下：
数据对象：D＝{ ai | ai 拒绝舌尖上的浪费手抄报∈ElemSet, i=1,2,...,n, n≥0 }
纸船的折法数据关系： R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n }
（约定an 端为栈顶，a1 端为栈底。）
基本操作：
void clear();//初始化操作
bool push(const Elem&it);//插入元素操作
bool pop（const Elem&it）;//删除操作
bool topValue(Elem&it);//获取栈顶元素的值
为了存储中缀表达式，构建一个树的ADT
数据对象D：D是具有相同特性的数据元素的集合
数据关系R:
若D为空集，则称为空树 。 否则:
(1)在D中存在唯一的称为根的数据元素root；
网络营销人员 (2) 当n>1时，其余结点可分为m (m>0)个互 不相交的有限集T1, T2, …, Tm，其中每一佛山旅游景点 棵子集本身又是一棵符合本定义的树，称为根root的子树。
基本操作：
void insert(const char&);
void clear();
算法基本思想
1先将用户输入的中缀表达式存入一个二叉树中，然后对该二叉树进行一次后序遍历，即可得到该表达式的后序表达式，然后输出该后序表达式即可；
2建树过程中构造两个栈S1和S2，S1用来存放节点指针，S2用来存储操作符；遍历表达式时，如果遇到操作数，则建立节点并将其压入栈S1中。遇到操作符则将其压入操作符栈S2中，若栈顶还有操作符则弹出该操作符进行优先度比较，将优先度高的先放入栈中。弹出
S2栈顶的操作符，建立节点，并弹出两个S1栈顶的节点，将操作符结点的左右指针域指向它们。直到操作符域为空。
3求后缀表达式值时再构造一个栈S用来存放操作数。因为在定义 数据类型的时候，要存储操作符，所以操作数也是用char类型存储的。后序遍历到操作数是需要将其转换为float型并压入栈中。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论