数据结构a十进制整数四则运算计算器

东北大学信息科学与工程学院数据结构课程设计报告题目 十进制整数四则运算计算器课题组长 余灏然课题组成员 魏嘉 张越专业名称 计算机科学与技术班级 计算机1307指导教师 杨雷2015 年 1月 课程设计任务书题目：十进制整数四则运算计算器问题描述：由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。设计要求：设计十进制整数四则运算计算器。（1）采用二叉树、栈等数据结构。（2）给定表达式字符串，生成二叉链表的表达式二叉树。（3）对表达式二叉树采用后序遍历求值并输出。（4）可以考虑加入复数四则运算功能。（5）其它完善性功能。指导教师签字：2014年12月28日 目录1 课题概述11.1 课题任务11.2 课题原理11.3 相关知识42 需求分析42.1 课题调研52.2 用户需求分析53 方案设计53.1 总体功能设计53.2 数据结构设计53.3 函数原型设计53.4 主算法设计53.5 用户界面设计54 方案实现64.1 开发环境与工具64.2 程序设计关键技术64.3 个人设计实现（按组员分工）4.3.1余灏然设计实现64.3.2 魏嘉设计实现94.3.3 张越设计实现115 测试与调试135.1 个人测试（按组员分工）135.1.1 余灏然测试135.1.2 魏嘉测试165.1.3 张越测试205.2 组装与系统测试255.3 系统运行256 课题总结266.1 课题评价266.2 团队协作266.3 个人设计小结（按组员分工）266.3.1 余灏然设计小结266.3.2 魏嘉设计小结276.3.3 张越设计小结277 附录A 课题任务分工28A-1 课题程序设计分工28A-2 课题报告分工29附录C 用户操作手册（可选）30C.1 运行环境说明30C.2 操作说明30 1 课题背景1.1 课题任务【问题描述】由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。【设计要求】设计十进制整数四则运算计算器。（1）采用二叉树、栈等数据结构。（2）给定表达式字符串，生成二叉链表的表达式二叉树。（3）对表达式二叉树采用后序遍历求值并输出。（4）可以考虑加入复数四则运算功能。（5）其它完善性功能。1.2 课题原理用二叉链表处理表达式字符串，用栈处理括号在表达式计算时的优先级问题，并且使用MFC编程语言实现可视化。1.2.1二叉链表1.2.2栈处理符号表达式1.2.3MFC编程语言实现可视化用MFC语言中对按钮Button功能的添加，将外界输入的由数字09，符号“+”、“-”、“*”、“/”、“（”、“）”构成的表达式传入编辑框中的变量CString中。与此同时，可以使用退格键“”执行退格功能和清屏键执行清屏功能。并且使用“=”按钮时，对输入的表达式进行计算。最终，由编辑框输出计算结果。流程图如下流程图1流程图21.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 dmax)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 余灏然设计实现数据结构定义和描述：反转表达式及转换前缀表达式：#includehead.h#includefuhao.cpp#includeiostreamusing namespace std;void turn(Stack &T,char dmax);void change(Stack T,Stack &S);void turn(Stack &T,char dmax) /字符串输入表达式且压栈int h,r=0; /h用于重置数字，r用于计位置data b;while(1)if(dr=0) break;if( In(dr) ) b.k=2;b.s=dr+;Push(T,b);elseh=0; while(dr!=0)if(dr=+|dr=-|dr=*|dr=/|dr=(|dr=) break;h*=10;switch(dr)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|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 魏嘉设计实现符号相关操作：#includeiostreamusing 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=; break; case-:if(b=*|b=/|b=() c=; break; case*:if(b=() c=; break; case/:if(b=() c=; break; case(:if(b=)c=; else c=; break; case=:if(b=) c=; else c=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 张越设计实现建立二叉链表：#includehead.h#includefuhao.cpp#includeiostreamusing namespace std;void turn(Stack &T,char dmax);void change(Stack T,Stack &S);typedef struct Nodedata 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); T-p=b; CreatTree(T-lchild,S); CreatTree(T-rchild,S); return(1);栈的创建与操作：#includeiostreamusing namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define max 50typedef struct Ndataint k; / 判断用 k=1: 数字 2：符号 3：返回,用于二叉树的建立int i; /数字char s; /符号data;typedef struct NStackdata *base;data *top;int stacksize;Stack;int InitStack(Stack & S)S.base=(data*)malloc(STACK_INIT_SIZE * sizeof(data) );if(!S.base) exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;int GetTop(Stack S,data &e)if(S.top=S.base) return 0;e= *(S.top-1);return 1;int Push(Stack &S,data e)if(S.top-S.base=S.stacksize)S.base=(data*)realloc(S.base,(S.stacksize + STACKINCREMENT)* sizeof(data);if(!S.base) exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top+) = e;return 1;int Pop(Stack &S,data &e)if(S.top=S.base) return 0;e= *-S.top;return 1;void ClearStack(Stack &S) /把栈置空，只留栈底data e;while(1)GetTop(S,e);if(e.k=-1 ) break;Pop(S,e);5 测试与调试5.1 个人测试（按组员分工）5.1.1 余灏然测试#includehead.h#includefuhao.cpp#includeiostreamusing namespace std;void turn(Stack &T,char dmax);void change(Stack T,Stack &S);void main()static char dmax; Stack T,S,P; / T为反转栈，S用于输出先序表达式InitStack(T);InitStack(S);InitStack(P);data a,b,c;b.k=2 ; b.s=; a.k=1;Push(T,b);Push(S,b);Push(P,b);coutd;turn(P,d);cout前缀表达式:;while(1)Pop(P,c);if(c.k=2&c.s=) break;if(c.k=1) coutc.i;if(c.k=2) coutc.s;turn(T,d); /反转，将栈由栈顶输出到栈底的顺序即为反转顺序change(T,S); /转化成前序表达式,T为转变前，S为转变后coutendl前缀表达式:;while(1)Pop(S,a);if(a.k=2&a.s=) break;if(a.k=1) couta.i;if(a.k=2) couta.s;coutendl;void turn(Stack &T,char dmax) /字符串输入表达式且压栈int h,r=0; /h用于重置数字，r用于计位置data b;while(1)if(dr=0) break;if( In(dr) ) b.k=2;b.s=dr+;Push(T,b);elseh=0; while(dr!=0)if(dr=+|dr=-|dr=*|dr=/|dr=(|dr=) break;h*=10;switch(dr)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|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);测试结果：5.1.2 魏嘉测试符号相关操作：#includeiostreamusing namespace std;char Compare(char a,char b);int In(char c);int Operate(int b,char x,int a);void main()int i,j,k;char a,b,s;while(1)couti;if(i=1)coutab;s=Compare(a,b);cout优先级：sendlendl;if(i=2)couts;if(In(s) cout是运算符endl;else cout非运算符endl;if(i=3)coutjk;couts;j=Operate(k,s,j);cout结果为jendl;/*判断运算的优先顺序*/char Compare(char a,char b) char c; switch(a) case+:if(b=*|b=/|b=() c=; break; case-:if(b=*|b=/|b=() c=; break; case*:if(b=() c=; break; case/:if(b=() c=; break; case(:if(b=)c=; else 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;#includehead.h#includefuhao.cpp#includeiostreamusing namespace std;void turn(Stack &T,char dmax);void change(Stack T,Stack &S);typedef struct Nodedata p;struct Node *lchild,*rchild;Node,*Tree;void main()void PostOrder(Tree T,Stack &S);void main2(Tree &T);Stack P; Tree T;InitStack(P);data b;b.k=2 ; b.s=; Push(P,b);main2(T);PostOrder(T,P);GetTop(P,b);cout表达式值为b.ilchild,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);测试结果：5.1.3 张越测试#includehead.h#includefuhao.cpp#includeiostreamusing namespace std;void turn(Stack &T,char dmax);void change(Stack T,Stack &S);typedef struct Nodedata p;struct Node *lchild,*rchild;Node,*Tree;void main()Stack main1();int CreatTree(Tree &T,Stack &S);Stack S;Tree T;InitStack(S);data b,c;int i;b.k=2 ; b.s=;Push(S,b);S=main1();CreatTree(T,S);cout表达式树建立成功！endl;coutp;if(c.k=1) coutc.iendl;if(c.k=2) coutc.sendl;couti;if(i=1) T=T-lchild;if(i=2) T=T-rchild;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); T-p=b; CreatTree(T-lchild,S); CreatTree(T-rchild,S); return(1);测试结果：栈的创建与操作：#includeiostreamusing namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define max 50typedef struct Ndataint k; / 判断用 k=1: 数字 2：符号 3：返回,用于二叉树的建立int i; /数字char s; /符号data;typedef struct NStackdata *base;data *top;int stacksize;Stack;int InitStack(Stack & S)S.base=(data*)malloc(STACK_INIT_SIZE * sizeof(data) );if(!S.base) exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;int GetTop(Stack S,data &e)if(S.top=S.base) return 0;e= *(S.top-1);return 1;int Push(Stack &S,data e)if(S.top-S.base=S.stacksize)S.base=(data*)realloc(S.base,(S.stacksize + STACKINCREMENT)* sizeof(data);if(!S.base) exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top+) = e;return 1;int Pop(Stack &S,data &e)if(S.top=S.base) return 0;e= *-S.top;return 1;void ClearStack(Stack &S) /把栈置空，只留栈底data e;while(1)GetTop(S,e);if(e.k=-1 ) break;Pop(S,e);void main()int i;Stack T;InitStack(T);cout创建栈成功!endl;data a,b;a.k=-1;a.i=-1;Push(T,a);while(1)couti;if(i=1)coutb.kb.i;Push(T,b);cout已成功存入栈里!endl;if(i=2)GetTop(T,b);coutb.k b.iendl;if(i=3)Pop(T,b);coutb.k b.iendl;if(i=4)ClearStack(T);cout置空成功！endl;getchar();getchar();if(i=5) break;测试结果：5.2 组装与系统测试5.3 系统运行6 课题总结6.1 课题评价按照课题的要求，我们组同学进行了分工，实现了其所规定的设计要求，并且有所拓展，运用课本上的知识及学习了一些本来未曾接触的知识，运用陌生的类模板实现了掌握较为熟练的功能。6.2 团队协作 由于需要学习新的知识-MFC编程语言，在完成项目过程中，我们进行了明确的分工，以确保高效，每个人对新知识的学习，之后汇总，按照所学分配任务，高效地完成了任务。6.3 个人设计小结（按组员分工）6.3.1余灏然设计小结 经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。这次课程设计使我收获了很多，不仅有技术上的，还有做事方面的，我学会了不骄不躁去完成好每一件事。这次的课程设计，加强了我们动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了，而且还可以记住很多东西。总之这次课设对我们现在的学习及以后的工作无疑有莫大的帮助。6.3.2魏嘉设计小结1、上好实验课，多实践，充分利用上机机会，查漏补缺，培养一些好的习惯，日后会在工作中受益。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。5、 在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。6.3.3张越设计小结通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣。设计一个程序靠课堂上所学的知识是远远不够的，