东北大学信息科学与工程学院
数据结构课程设计报告题目十进制整数四则运算计算器课题组长余灏然
课题组成员魏嘉张越
专业名称计算机科学与技术
班级计算机1307
指导教师杨雷
2015 年1月
课程设计任务书
题目:
十进制整数四则运算计算器
问题描述:
由输入的四则运算表达式字符串,动态生成算术表达式所对应的二叉树,通过表达式二叉树自动求值并输出。
设计要求:
设计十进制整数四则运算计算器。
(1)采用二叉树、栈等数据结构。
(2)给定表达式字符串,生成二叉链表的表达式二叉树。
(3)对表达式二叉树采用后序遍历求值并输出。
(4)可以考虑加入复数四则运算功能。
(5)其它完善性功能。
指导教师签字:
2014年12月28日
目录
1 课题概述 (1)
1.1 课题任务 (1)
1.2 课题原理 (1)
1.3 相关知识 (4)
2 需求分析 (4)
2.1 课题调研 (5)
2.2 用户需求分析 (5)
3 方案设计 (5)
3.1 总体功能设计 (5)
3.2 数据结构设计 (5)
3.3 函数原型设计 (5)
3.4 主算法设计 (5)
3.5 用户界面设计 (5)
4 方案实现 (6)
4.1 开发环境与工具 (6)
4.2 程序设计关键技术 (6)
4.3 个人设计实现(按组员分工)
4.3.1余灏然设计实现 (6)
4.3.2 魏嘉设计实现 (9)
4.3.3 张越设计实现 (11)
5 测试与调试 (13)
5.1 个人测试(按组员分工) (13)
5.1.1 余灏然测试 (13)
5.1.2 魏嘉测试 (16)
5.1.3 张越测试 (20)
5.2 组装与系统测试 (25)
5.3 系统运行 (25)
6 课题总结 (26)
6.1 课题评价 (26)
6.2 团队协作 (26)
6.3 个人设计小结(按组员分工) (26)
6.3.1 余灏然设计小结 (26)
6.3.2 魏嘉设计小结 (27)
6.3.3 张越设计小结 (27)
7 附录A 课题任务分工 (28)
A-1 课题程序设计分工 (28)
A-2 课题报告分工 (29)
附录C 用户操作手册(可选) (30)
C.1 运行环境说明 (30)
C.2 操作说明 (30)
1 课题背景
1.1 课题任务
【问题描述】
由输入的四则运算表达式字符串,动态生成算术表达式所对应的二叉树,通过表达式二叉树自动求值并输出。
【设计要求】
设计十进制整数四则运算计算器。
(1)采用二叉树、栈等数据结构。
(2)给定表达式字符串,生成二叉链表的表达式二叉树。
(3)对表达式二叉树采用后序遍历求值并输出。
(4)可以考虑加入复数四则运算功能。
(5)其它完善性功能。
1.2 课题原理
用二叉链表处理表达式字符串,用栈处理括号在表达式计算时的优先级问题,并且使用MFC编程语言实现可视化。
1.2.1二叉链表
1.2.2栈处理符号表达式
1.2.3MFC编程语言实现可视化
用MFC语言中对按钮Button功能的添加,将外界输入的由数字0~9,符号“+”、“-”、“*”、“/”、“(”、“)”构成的表达式传入编辑框中的变量CString 中。与此同时,可以使用退格键“←”执行退格功能和清屏键执行清屏功能。并且使用“=”按钮时,对输入的表达式进行计算。最终,由编辑框输出计算结果。
流程图如下
流程图1
开始
输入表达式
表达式入栈
(反转表达式)
转化为先序表
达式
后序遍历求值
输出计算结果
结束
流程图2
1.3相关知识
生成二叉链表,树的后序遍历,MFC编程语言实现可视化
2需求分析
2.1 课题调研
整数十进制四则运算计算器,用户输入算式程序程序运行并输出运算结果。
2.2 用户需求分析
(1)用户可以通过MFC按钮输入多项式;
(2)可输入带括号的运算;
(3)该程序应该有对用户错误输入的辨别纠错功能;
(4)程序应具有演示功能和调试功能。
(5)程序应具有良好的人机接口。
(6)程序应能友好的展现结果。
3方案设计
3.1 总体功能设计
十进制整数四则运算
3.2 数据结构设计
栈结构,用来储存多项式及生成树;
树结构,用来后序遍历以求多项式的值。
3.3 函数原型设计
函数原型参数说明功能描述
void turn(Stack &T,char d[max])
void change(Stack
T,Stack &S)栈T,字符数组d
[]
栈T,栈S
将输入的多项式压栈并转化为前缀
表达式
int CreatTree(Tree
&T,Stack &S)
Void PostOrder(Tree
T,Stack &S)
树T,栈S 建立二叉链表并且后序遍历求值
3.4主算法设计
⑴将输入的表达式压栈,并将其转换为前缀表达式;
⑵由前缀表达式生成二叉链表;
⑶后序遍历二叉树求值。
3.5 用户界面设计
使用MFC编程语言设计界面如下:
4 方案实现
4.1 开发环境与工具
主要编程环境:Blend for Visual Studio 2013
编程工具:C++。
4.2 程序设计关键技术
⑴将输入的表达式压栈,并将其转换为前缀表达式;
⑵由前缀表达式生成二叉链表;
⑶后序遍历二叉树求值。
4.3 个人设计实现(按组员分工)
4.3.1 余灏然设计实现
数据结构定义和描述:
反转表达式及转换前缀表达式:
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;
void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
void turn(Stack &T,char d[max]) //字符串输入表达式且压栈
{
int h,r=0; //h用于重置数字,r用于计位置
data b;
while(1)
{
if(d[r]=='\0') break;
if( In(d[r]) )
{
b.k=2;
b.s=d[r++];
Push(T,b);
}
else
{
h=0;
while(d[r]!='\0')
{
if(d[r]=='+'||d[r]=='-'||d[r]=='*'||d[r]=='/'||d[r]=='('||d[r]==')') break;
h*=10;
switch(d[r])
{
case '1': h+=1;break;
case '2': h+=2;break;
case '3': h+=3;break;
case '4': h+=4;break;
case '5': h+=5;break;
case '6': h+=6;break;
case '7': h+=7;break;
case '8': h+=8;break;
case '9': h+=9;break;
case '0': h+=0;break;
default: cout<<"表达式有误!"; exit(0);
}
r++;
}
b.k=1;
b.i=h;
Push(T,b);
}
}
}
void change(Stack T,Stack &S) //转前置表达式
{
Stack P;
InitStack(P);
data a,b,c;
a.k=2 ; a.s='=';
Push(P,a);
while(1)
{
Pop(T,b);
if(b.k==2 && b.s=='=') break;
if(b.k==1) { Push(S,b);continue; }
if(b.k==2)
{
if( b.s==')' ) { Push(P,b);continue; }
if( b.s!='('&& b.s!=')')
{
while(1)
{
GetTop(P,c);
if( Compare(b.s,c.s)=='>'||Compare(b.s,c.s)=='=') {Push(P,b);break;}
else { Pop(P,c); Push(S,c);}
}
}
if( b.s=='(' )
{
while(1)
{
Pop(P,c);
if(c.k==2 && c.s==')') break;
Push(S,c);
}
}
}
}
while(1)
{
GetTop(P,c);
if(c.k==2 && c.s=='=') break;
Pop(P,c);
Push(S,c);
}
}
4.3.2 魏嘉设计实现
符号相关操作:
#include"iostream"
using namespace std;
char Compare(char a,char b);
int In(char c);
int Operate(int b,char x,int a);
/*判断运算的优先顺序*/
char Compare(char a,char b)
{
char c;
switch(a)
{
case'+':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'-':if(b=='*'||b=='/'||b=='(')
c='<';
else c='>';
break;
case'*':if(b=='(')
c='<';
else c='>';
break;
case'/':if(b=='(')
c='<';
else c='>';
break;
case'(':if(b==')')c='=';
else c='<';
break;
case')':c='>';
break;
case'=':if(b=='=')
c='=';
else c='<';
break;
}
return c;
}
int In(char c){
if(c=='+' || c=='-' || c=='*'|| c=='/'||c=='('||c==')'||c=='=')
return 1;
else return 0;
}
int Operate(int b,char x,int a)
{
int z;
switch(x){
case'+': z=a+b;break;
case'-': z=a-b;break;
case'*': z=a*b;break;
case'/': z=a/b;break;
}
return z;
}
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;
void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;
后序遍历求值:
void PostOrder(Tree T,Stack &S) //利用递归,后序遍历并求值,T为二叉树,S为存储用的栈
{
data a,b,c,d;
if(T!=NULL)
{
PostOrder(T->lchild,S);
PostOrder(T->rchild,S);
c=T->p;
if(c.k==1) Push(S,c);
if(c.k==2)
{
Pop(S,b);Pop(S,a);
d.k=1;d.i=Operate(b.i,c.s,a.i);
Push(S,d);
}
}
}
4.3.3 张越设计实现
建立二叉链表:
#include"head.h"
#include"fuhao.cpp"
#include"iostream"
using namespace std;
void turn(Stack &T,char d[max]);
void change(Stack T,Stack &S);
typedef struct Node{
data p;
struct Node *lchild,*rchild;
}Node,*Tree;
int CreatTree(Tree &T,Stack &S) //建立二叉链表
{
data b,c;
Pop(S,b);
if(b.k==1) //当遇数字时,在后面补两个空位,用于建立二叉树{ c.k=3; Push(S,c); Push(S,c);}
if(b.k==3) T=NULL;
else
{
if(!(T=(Node*)malloc(sizeof(Node)))) exit(-1);
第四章串 一.选择题 1.若串S='software',其子串的数目是() A.8 B.37 C.36 D.9 2.设有两个串p和q,求q在p中首次出现的位置的运算称作() A.连接B.模式匹配C.求串长D.求子串 3.设字符串S1=“ABCDEFG”,S2=“PQRST”,则运算: S=CONCAT(SUBSTR(S1,2,LEN(S2));SUBSTR(S1,LEN(S2),2));后的串值为() A.A BCDEF B.BCDEFG C.BCDPQRST D. BCDEFEF 4.下面的说法中,只有()是正确的 A.串是一种特殊的线性表B.串的长度必须大于零 C.串中元素只能是字母D.空串就是空白串 5.两个字符串相等的条件是() A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等,并且两串包含的字符相同 D.两串的长度相等,并且对应位置上的字符相同 二.填空题 1.串“ababcbaababd”的next函数值为,nextval函数值为。2.子串的长度为。 第五章数组和广义表 一.选择题 1.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1 到8 ,j的值为1 到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=() A. 808 B. 818 C. 1010 D. 1020 3.对稀疏矩阵进行压缩存储目的是() A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度 4.假设以三元组表表示稀疏矩阵,则与如图所示三元组表对应的4×5的稀疏矩阵是(注:矩阵的行列下标均从1开始)()
简单的四则运算计算器程序
注:1、报告内的项目或内容设置,可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
附件:程序源代码 // sizheyunsuan.cpp : Defines the entry point for the console application. #include
计算器模拟系统设计 学生:XXX 指导教师:XXX 内容摘要:本设计是基于51系列的单片机进行的简易计算器系统设计,可以完成计算器的键盘输入,进行加、减、乘、除3位无符号数字的简单四则运算,并在LED 上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件选择AT89C51单片机和 74lS164,输入用4×4矩阵键盘。显示用5位7段共阴极LED静态显示。软件从分析计算器功能、流程图设计,再到程序的编写进行系统设计。选用编译效率最高的Keil 软件用汇编语言进行编程,并用proteus仿真。 关键词:LED 计算器 AT89C51芯片 74LS164
Calculator simulation system desig n Abstract:The design is a simple calculator based on 51 series microcontroller system design, to complete the calculator keyboard input, add, subtract, multiply, and in addition to three unsigned numeric simple four operations, and the corresponding result will be displayed on the LED. The design process of hardware and software aspects of the synchronous design. Hardware choose AT89C51 microcontroller and 74ls164--enter the 4 × 4 matrix keyboard. Static display with five 7-segment common cathode LED display. Software calculator function from the analysis, flow charts, design, and then program the preparation of system design. Selected to compile the most efficient Keil software in assembly language programming, and with proteus simulation. Keywords: LED calculator AT89C51 chip 74LS164
吉首大学课程设计 课程设计名称:简单的计算器 专业班级: 10 网络工程 学生姓名:胡申城唐茂林赖佳 学号:20104045049 20104045006 201040450 指导教师:鲁荣波老师 课程序设计时间:2011.12.18-2011.12.25
目录 一内容 (1) 二.设计要求 (2) 三.计算器的算法 (2) 四..流程图 (5) 五.源程序 (7) 六.执行结果 (8) 七.课程设计总结 (3) 八.参考书目 (3)
一、内容 编写一个功能基本完善的计算器程序,支持四则运算、乘方开方、指数对数等运算,支持带括号的表达式。 二、设计要求 1) 程序采用字符界面 2) 显示功能菜单,用户指定键即可进入相应功能 3) 每次计算完成后输出一个提示符,要计算的数字或表达式由用户在提示后面输入 4) 用户输入完按回车立即显示计算结果 三、计算器的算法 我们现在用的计算器多是一个数一个运算符的输入输出的。一个比较具有现实意义的计算器,应该具有如下功能: 1.能够实现整数的四则运算:如:1+6-9*4+4/3 2.能够实现小数的四则运算:如:0.2+7-4 这样的计算器基本可以使用在我们生活中。如果我们按照栈的使用来描述一下表达式的进栈出栈问题: 表达式例如:1+9*4/4-5。 假设有栈D和数组S;S中放运算数,D栈放入运算符,优先级高的现运算,四则运算中,*和/优先级最高。 第一步:扫描到‘1’,是运算数,放入S; 第二步:扫描到‘+‘进入D
第三步:扫描到9;进S 第四步:扫描‘*’,因为乘比加优先级高,所以9出栈实现:9*4,把结果入S, 第五步:扫描到/,同样计算S的栈顶元素出栈,实现36/4,把结果如S 第六步:扫描到—,进入D栈; 第七步:扫描到‘5’,进S 第八步:扫描到‘\0’,为结束符;把S栈顶元素栈S1,D顶元素出栈,然后S栈顶元素在出栈,实现减操作,接着S栈顶元素出栈,实现加操作。 具体进出栈如图: Next 为下一个字符或数字,run表示运行,空为不操作S[] D S[] D S[] D S[] D S[] D S[] top t top 9 top 36 top 4 - -1 top base 1 + 1 + 1 + 1 + 1 + 0 top top next + 9 * 4 / 4 - 5 = run 9*4 36/4 4-5 -1+1 表1-1 运算数运算符进栈、出栈
暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午~月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性; 熟悉二叉树的各种存储结构的特点及适用范围; 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系,熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件,写出后序遍历的非递归算法(提示:为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈)。 6.39假设在二叉链表的结点中增设两个域:双亲域以指示其双亲结点; 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境:Microsoft Visual Studio 2012 (四)源程序
6.37: #include
基于单片机实现的四则运算计算器 姓名 学号: 班级: 专业名称:测控技术与仪器 指导教师: 东北大学 2016年1月
课程设计(论文)任务书课程设计(论文)题目:基于单片机实现的四则运算计算器 基本内容和设计要求: 1、主机的矩阵键盘输入数和运算符号,从机显示运算结果。 2、主从单片机串行通信系统,并在LCD上显示运算内容及结果。 3、计算结果超过十位数字则显示错误。 4、运算除法时,结果只取整数,不是四舍五入。 5、有清零功能。
目录 课程设计(论文)任务书................................................................................................ i i 摘要 (1) 第1章绪论 (2) 1.1计算器简介 (2) 1.2设计主要内容 (2) 第2章系统硬件设计 (4) 2.1硬件组成 (4) 2.2输入模块 (4) 2.3输出模块 (5) 2.4运算模块 (5) 第3章系统软件设计 (7) 3.1 主程序 (7) 3.1.1主程序框图及初始化 (7) 3.1.2LCD程序框图及初始化 (8) 3.1.3键盘程序框图及初始化 (9) 3.1.4运算程序框图 (10) 第4章调试测试与实验分析 (11) 4.1 计算器调试 (11) 参考文献 (12) 心得体会 (13) 附录硬件原理图及PCB图 (14) 附录程序清单 (15) 附录实物照片 (28)
摘要 单片机的出现是计算机制造技术高速发展的产物,它是嵌入式控制系统的核心,如今,它已广泛的应用到我们生活的各个领域,电子、科技、通信、汽车、工业等。本设计是基于89C52RC单片机来进行的四则运算计算器系统设计,可以完成计算器的键盘输入,进行加、减、乘、除的基本四则运算,并在LCD1602液晶显示屏上显示相应的结果。本电路采用89C52RC单片机为主要控制电路,利用4*4矩阵键盘作为计算器以及运算符的输入。显示采用字符LCD静态显示。软件用C语言编程,并用开发板进行演示。 关键词:计算器,89C52RC单片机,LCD,矩阵键盘
目录 第一章设计目的及任务要求..................................................................................... 错误!未定义书签。 设计目的................................................... 错误!未定义书签。 设计任务................................................... 错误!未定义书签。 课设要求................................................... 错误!未定义书签。第二章设计思路............................................... 错误!未定义书签。 设计总体框图............................................... 错误!未定义书签。 设计原理................................................... 错误!未定义书签。 计算其原理............................................. 错误!未定义书签。 数码显示原理........................................... 错误!未定义书签。 八位数码管扫描的原理................................... 错误!未定义书签。第三章设计源程序及分析....................................... 错误!未定义书签。 计算器模块................................................. 错误!未定义书签。 计算器源程序........................................... 错误!未定义书签。 计算器程序分析......................................... 错误!未定义书签。 数码管显示部分...................................................................................................... 错误!未定义书签。 数码管显示源程序.......................................................................................... 错误!未定义书签。 数码管显示程序分析..................................................................................... 错误!未定义书签。 循环扫描模块........................................................................................................... 错误!未定义书签。 循环扫描程序................................................................................................... 错误!未定义书签。 循环程序分析................................................................................................... 错误!未定义书签。 总程序及其分析...................................................................................................... 错误!未定义书签。第四章时序仿真和结果验证..................................................................................... 错误!未定义书签。
HTML5+JavaScript: