- 1、本文档共22页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构实验报告三
——简易计算器(二叉树)
姓名:任子龙 学号:1120140167 班级一、需求分析
(1)问题描述
由键盘输入一算术表达式,以中缀形式输入,试编写程序将中缀表达式转换成一棵二叉表达式树,通过对该二叉树的后序遍历求出计算表达式的值。
(2)基本要求
a.要求对输入的表达式能判断出是否合法,不合法要有错误提示信息。
b.将中缀表达式转换成二叉表达式树。
c.后序遍历求出表达式的值。
(3)数据结构与算法分析
一棵表达式树,它的树叶是操作数,如常量或变量名字,而其他的结点为操作符。
a.建立表达式树。二叉树的存储可以用顺序存储也可用链式存储。当要创建二叉树时,先从表达式尾部向前有哪些信誉好的足球投注网站,找到第一个优先级最低的运算符,建立以这个运算符为数据元素的根结点。注意到表达式中此运算符的左边部分对应的二叉绔为根结点的左子树,右边部分对应的是二叉绔为根结点的右子树,根据地这一点,可用递归调用自己来完成对左右子树的构造。
b.求表达式的值。求值时同样可以采用递归的思想,对表达式进行后序遍历。先递归调用自己计算左子树所代表的表达式的值,再递归调用自己计算右子树代表的表达式的值,最后读取根结点中的运算符,以刚才得到的左右子树的结果作为操作数加以计算,得到最终结果。
(4)测试
a.加减运算
输入:6+9-5 输出:10
b.乘除运算
输入:5.6*2.7/2 输出:7.56
c.四则混合运算
输入:(2+3)*8-3/2 输出:23.5
d.非法输入
输入:(5+6(*5 输出:括号不匹配!
1.2问题分析
与之前利用栈实现计算器功能不同,本实验采取的方法是:将中缀表达式转换成一棵二叉表达式树,通过对该树的后序遍历求出计算表达式的值。所以,实验的重点是如何“将中缀表达式转换成一棵二叉表达式树”;
如上图所示,该二叉表达式树表示的是计算式(5+2)*3。可以看出,操作数均为叶子结点,其它结点为操作符;构建二叉树的整体思路是:(1)将中缀表达式转化为后缀表达式;(2)利用(1)中的后缀表达式,在此基础上构建二叉表达式树。
最后的求值,可以通过递归调用函数,后序遍历二叉树来完成。
二、概要设计
2.1抽象数据类型定义
本程序主要用到的数据结构是二叉链表,所以先行定义链表结点,其中每一个节点包含两个数据域和两个指针域,数据域分别存放char型变量和float型变量,相对应是运算符和操作数;指针域分别指向两个左右孩子。
struct node{
char data;
float number;
struct node *left;
struct node *right;
};
另外,考虑到程序还需转换后缀表达式,所以又建立了另一种结点类型变量,并定义其类型的数组array[20]:
struct oprtnumber{
char sign; //存放符号型变量
float number; //存放浮点数
}array[20];
2.2主程序流程
主函数流程如下:
int main()
{
char *b,a[100],*t;
b=convert(); //中缀表达式转为反序后缀表达式
do
{ 完成反序后缀式的逆向 ;
}
T=create(T,a); //create()函数创建二叉链表
postordertraverse(T);//后序遍历进行计算
输出结果;
} //main
2.3程序模块调用关系
具体关系如下图所示:
三、详细设计
3.1主函数的具体过程
int main()
{ struct node *T;
flag=0;
T=(struct node *)malloc(sizeof(struct node));
char *b,a[100],*t;
int i; b=convert(); //中缀表达式转为反序后缀表达式
for(t=b;*t!=\0;t++);
i=0;
do
{ t--;
a[i]=*t; i++;
}
while(t!=b);
a[i]=\0;//完成反序后缀式的逆向
T=create(T,a); //create()函数创建二叉链表
postordertraverse(T);//后序遍历进行计算
pr
您可能关注的文档
- 第八章危险货物运输选读.pptx
- 高三一轮复习:语言表达简明、连贯、得体、准确、鲜明、生动汇总.pptx
- 第二单元无处不在的能量知识点选读.docx
- 1.2防腐与阻垢技术选读.ppt
- 高三一轮复习《古代希腊、罗马的政治文明》汇总.ppt
- 4风化作用选读.ppt
- 电子电器产品营销实务1汇总.ppt
- 第二讲++创新系统与研发地点的选择选读.pptx
- 1.2功率放大器的电路组成和工作特性选读.ppt
- 4钢的热处理选读.ppt
- 2023年度无锡职业技术学院单招数学预测复习含答案详解【实用】.docx
- 2023年度无锡职业技术学院单招数学预测复习含答案详解【实用】.docx
- 2023年度昆山登云科技职业学院单招《数学》测试卷含完整答案详解【历年真题】.docx
- 2021年高中物理新人教版必修第一册 第十单元 静电场中的能量 达标检测卷 B卷 教师版.doc
- 2023年度无锡科技职业学院单招《英语》题库【全国通用】附答案详解.docx
- 2023年度无锡科技职业学院单招《英语》模拟题库附参考答案详解【B卷】.docx
- 2023年度日照航海工程职业学院单招《数学》检测卷附答案详解(轻巧夺冠).docx
- 2023年度无锡职业技术学院单招《数学》题库检测试题打印附完整答案详解(考点梳理).docx
- 2023年度无锡工艺职业技术学院单招考试文化素质数学高分题库附参考答案详解【考试直接用】.docx
- 小学科学苏教版《降落伞》全文标准课件1.pptx
最近下载
- 数字温度计设计.doc VIP
- 2023年深圳大学软件工程专业《操作系统》科目期末试卷A(有答案).docx VIP
- 民用建筑防爆设计标准.pdf VIP
- 品管圈报告书.docx
- 2023年深圳大学软件工程专业《操作系统》科目期末试卷B(有答案).docx VIP
- 2022年深圳大学软件工程专业《操作系统》科目期末试卷B(有答案).docx VIP
- 2023年深圳大学计算机科学与技术专业《操作系统》科目期末试卷A(有答案).docx VIP
- 工程联系单管理规定.pdf VIP
- 2023年深圳大学计算机科学与技术专业《操作系统》科目期末试卷B(有答案).docx VIP
- 10KV和以下电力工程施工组织方案.pdf VIP
文档评论(0)