【数据结构】【A】十进制整数四则运算计算器

【数据结构】【A】十进制整数四则运算计算器 东北大学信息科学与工程学院 数据结构课程设计报告 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目 十进制整数四则运算计算器 课题组长 余灏然 课题组成员 魏嘉 张越 专业名称 计算机科学与技术 班级 计算机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 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 设计 ......................................................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 开始 输入表达式 表达式入栈 (反转表达式) 转化为先序表 达式 后序遍历求值 输出计算结果 结束 流程图2 1.3相关知识 生成二叉链表，树的后序遍历，MFC编程语言实现可视化 2需求分析 4 2.1 课题调研 整数十进制四则运算计算器，用户输入算式程序程序运行并输出运算结果。 2.2 用户需求分析 (1)用户可以通过MFC按钮输入多项式; (2)可输入带括号的运算; (3)该程序应该有对用户错误输入的辨别纠错功能; (4)程序应具有演示功能和调试功能。 (5)程序应具有良好的人机接口。 (6)程序应能友好的展现结果。 3方案设计 3.1 总体功能设计 十进制整数四则运算 3.2 数据结构设计 栈结构，用来储存多项式及生成树; 树结构，用来后序遍历以求多项式的值。 3.3 函数原型设计 函数原型 参数说明 功能描述 void turn(Stack 栈T，字符数组d 将输入的多项式压栈并转化为前缀 &T,char d[max]) [] 表达式 void change(Stack 栈T，栈S T,Stack &S) int CreatTree(Tree 树T，栈S 建立二叉链表并且后序遍历求值 &T,Stack &S) Void PostOrder(Tree T,Stack &S) 3.4主算法设计 ?将输入的表达式压栈，并将其转换为前缀表达式; ?由前缀表达式生成二叉链表; ?后序遍历二叉树求值。 3.5 用户界面设计 使用MFC编程语言设计界面如下: 5 4 方案实现 4.1 开发环境与工具 主要编程环境:Blend for Visual Studio 2013 编程工具:C++。 4.2 程序设计关键技术 ?将输入的表达式压栈，并将其转换为前缀表达式; ?由前缀表达式生成二叉链表; ?后序遍历二叉树求值。 4.3 个人设计实现(按组员分工) 4.3.1 余灏然设计实现 数据结构定义和描述: 反转表达式及转换前缀表达式: 6 #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++; 7 } 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); } } } } 8 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='<'; 9 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为存储用的栈 { 10 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); 11 T->p=b; CreatTree(T->lchild,S); CreatTree(T->rchild,S); } return(1); } 栈的创建与操作: #include"iostream" using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define max 50 typedef struct Ndata{ int k; // 判断用 k=1: 数字 2:符号 3:返回,用于二叉树的建立 int i; //数字 char s; //符号 }data; typedef struct NStack{ data *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) 12 { 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 余灏然测试 #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 main() { 13 static char d[max]; 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); cout<<"请输入表达式:"; cin>>d; turn(P,d); cout<<"前缀表达式:"; while(1) { Pop(P,c); if(c.k==2&&c.s=='=') break; if(c.k==1) 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 魏嘉测试 符号相关操作: #include"iostream" 16 using 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) { cout<<"请选择操作1.符号优先级判断 2.判断是否是符号 3.两个数的四 则运算 : "; cin>>i; if(i==1) { cout<<"请输入两个符号:"; cin>>a>>b; s=Compare(a,b); cout<<"优先级:"<>s; if(In(s)) cout<<"是运算符"<>j>>k; cout<<"请选择加减乘除:"; cin>>s; j=Operate(k,s,j); cout<<"结果为"<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); } } } 测试结果: 5.1.3 张越测试 #include"head.h" #include"fuhao.cpp" #include"iostream" using namespace std; 20 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 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<<"表达式树建立成功～"<p; if(c.k==1) cout<>i; 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; 21 else { if(!(T=(Node*)malloc(sizeof(Node)))) exit(-1); T->p=b; CreatTree(T->lchild,S); CreatTree(T->rchild,S); } return(1); } 测试结果: 栈的创建与操作: #include"iostream" using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define max 50 typedef struct Ndata{ int k; // 判断用 k=1: 数字 2:符号 3:返回,用于二叉树的建立 int i; //数字 char s; //符号 }data; typedef struct NStack{ data *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; 22 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() 23 { int i; Stack T; InitStack(T); cout<<"创建栈成功!"<>i; if(i==1) { cout<<"请输入2个数字:"; cin>>b.k>>b.i; Push(T,b); cout<<"已成功存入栈里!"< 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和工程设计方法。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。而且做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了，而且还可以记住很多东西。总之这次课设对我们现在的学习及以后的工作无疑有莫大的帮助。 6.3.2魏嘉设计小结 1、上好实验课，多实践，充分利用上机机会，查漏补缺，培养一些好的习惯，日后会在工作中受益。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 ，并在此基础上学会灵活运 用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 6.3.3张越设计小结 通过这次的程序设计，发现一个程序设计就是算法与数据结构的结合体，自己也开始对程序产生了前所未有的兴趣。设计一个程序靠课堂上所学的知识是远远不够的，还需要依靠课外的学习以及丰富。我在巩固了原有的理论知识上，又培养了灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，体会到自身知识和能力在实际中的应用和发挥。此次试验激发了创新意识，开发创造的能力和培养沟通能力，了解到团队合作的重要性。使我进一步熟悉了数据结构的设计应用。每一处编码都是在反复的熟悉数据结构的结构特性，及其语法、函数和程序设计思想的过程，对数据结构的学习和提高很有益处，并且使我明白了程序设计过程。 27 附录A 课题任务分工 课题程序设计分工 学号 姓名 程序设计函数原型、类 功能说明 20134005 余灏然 main() 字符串输入表达式且压栈 void turn(Stack &T,char 中缀表达式转前置表达式 d[max]) void change(Stack T,Stack &S) 20134003 魏嘉 比较符号优先级 char Compare(char a,char 进行计算 b) 后序遍历求值 int Operate(int b,char x,int a) Void PostOrder(Tree T,Stack &S) 20134007 张越 int CreatTree(Tree &T,Stack 生成表达式二叉链表 &S) 栈的初始化 int InitStack(Stack & S) 取栈顶元素 int GetTop(Stack S,data &e) 压栈 int Push(Stack &S,data e) 弹栈 int Pop(Stack &S,data &e) 把栈置空，只留栈底 void ClearStack(Stack &S) 28 课题报告分工 章节 内容 完成人 1 课题概述 1.1 课题任务 余灏然 1.2 课题原理 1.3 相关知识 2 需求分析 2.1 课题调研 魏嘉 2.2 用户需求分析 3 方案设计 3.1 总体功能设计 张越 3.2 数据结构设计 3.3 函数原型设计 3.4 主算法设计 3.5 用户界面设计 4 方案实现 4.1 开发环境与工具 张越 4.2 程序设计关键技术 4.3 个人设计实现(按组员分工) 4.3.1 余灏然 4.3.2 魏嘉 4.3.3张越 5 测试与调试 5.1 个人测试(按组员分工) 魏嘉 5.1.1 余灏然 5.1.2 魏嘉 5.1.3 张越 5.2 组装与系统测试 5.3 系统运行 6 课题总结 6.1 课题评价 余灏然 6.2 团队协作 6.3 下一步工作 6.4 个人设计心得(按组员分工) 6.4.1 余灏然 6.4.2 魏嘉 6.4.3 张越 29 附录C 用户操作手册 C.1 运行环境说明 Windows环境下运行 C.2 操作说明 用户需输入待运算表达式即可实现运算功能，具体如下图: 30