淮海工学院数据结构课程设计表达式求值(可浮点型,指数运算)

1、淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 表达式求值 姓 名： * 学 号： 201412* 专业班级： 软件工程 软件142 系 （院）： 计算机工程学院 设计时间： 2015.12.212016.1.4 设计地点： 计算机实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 22 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独

2、立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。所选课题：表达式求值问题描述：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只

3、含加减乘除等四种运算符，界限符有左右括号和表达式结束符“=”，如：（7+15）*（23-28/4）=。引入表达式结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 基本要求：（1） 从键盘读入一个合法的算术表达式，输出正确的结果。 （2） 显示输入序列和栈的变化过程。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、设计的题目要求达到一定工作量（

4、300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书1、 需求分析 功能需求 1.根据合法的表达式求出最终结果。 2.显示输入序列和栈的变化过程。 数据需求 1、输入的形式：表达式=(“=”是表达式结束符)； 2、输入值的范围：实数； 3、输出的形式：表达式=结果； 4、运算符 +、-、*、/,； 5、界限符：()、=

5、； 性能需求 在完成题目要求的基础上，扩充操作数的范围到实数。二、概要设计1、数据元素由于某些运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格按照从左到右的顺序进行运算，这就要求使用栈来执行正确的指令。ADT Stack数据对象：D=ai|aiElement，i=1,2,3,，n，n1且n属于整数数据关系：R1=|ai-1,aiD，i=2、n；约定an端为栈顶，ai端为栈底2、基本操作及作用(1)初始化栈int InitStack_f(Stack_f *s)/ 初始化数字栈int InitStack_c(Stack_c *s)/ 初始化运算符栈(2)入栈int Push_f(Sta

6、ck_f *s,float e)/数字入栈int Push_c(Stack_c *s,char e)/运算符入栈(3)出栈int Pop(S,x)/ 数字出栈int charPop(K,x)/ 运算符出栈(4)取栈顶元素int GetTop_f(Stack_f *s,float *e)/数字取栈顶元素int GetTop_c(Stack_c *s,char *e)/运算符取栈顶元素(5) 弹出栈顶元素int Pop_f(Stack_f *s,float *e)/弹出栈顶数字元素，e带值返回int Pop_c(Stack_c *s,char *e)/弹出栈顶运算符元素，e带值返回3、系统中的子程

7、序和功能说明：/比较运算符的优先级int precede(char Top_char,char s1_char);/将中缀表达式转化为后缀表达式int Translate(char *s1);/计算过程int Calculate(Stack_f *s,char *s2);/输出计算结果void result(Stack_f *s,char *str);/判断等号是否存在或有误int Judge(char *s);运算符的优先级12+-*/（）=+-*/（=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

8、, , , , , , , , , , !, =; /确定运算符的优先级switch(Top_char) / i为下面array的横标 case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break;case : i=4;break; case ( : i=5;break; case ) : i=6;break; case = : i=7;break; switch(s1_char)/ j为下面array的纵标 case + : j=0;break; case - : j=1;break; case

9、* : j=2;break; case / : j=3;break;case : j=4;break; case ( : j=5;break; case ) : j=6;break; case = : j=7;break; 返回优先级比较结果/中缀表达式转换为后缀表达式/in 中缀表达式/out 后缀表达式/return 1转换成功return 0转换失败int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;初始化运算符栈Optr;Push_c(&Optr,();while(s1i!=)if(s1i是数字或小数点的字

10、符) s2j+=s1i;if(s1i不是数字或小数点的字符)s2j+=空格;elseswitch(s1i) case(:将s1i压入运算符站;break; case):弹出运算符栈栈顶元素，将该元素赋值给t; break; while(t!=() s2j+=t;弹出运算符栈栈顶元素，将该元素赋值给t;break;default:while(取字符站栈顶元素，若优先级大于读入的运算符)弹出栈顶元素并赋值给t;s2j+=t;将t压入运算符栈;i+;弹出栈顶元素并赋值给t;表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!=() s2j+=t;弹出栈顶元素并赋值给t; 将s

11、2重新赋值给s1；s1i= =;s1i+1=0;return 1;/计算出最终结果/in 后缀表达式/out 运算结果/return 1计算成功return 0计算失败 int Calculate(Stack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!=)/ if(若为数值和小数点)则将其联合转换为浮点型后进栈；else 弹出数字栈栈顶元素弹出数字栈栈顶元素switch(s2i)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈case +:z=y+x;输出y+x=z;break;case -:z=y-x;输出y-x=z;b

12、reak;case *:z=y*x;输出y*x=z;break;case /:if(若除数为零) printf(ERROR !n); return 0; elsez=y/x;输出y*x=z; break; case :z=pow(y,x);输出yx=z;break;default: 输出符号不合法!; return 0; 将运算结果压入数字栈栈顶;i+;return 1;/写出最终结果/in中缀表达式，数字栈/out中缀表达式=最终结果void result(Stack_f *s,char *str) 取数字栈栈顶；输出最终结果；/判断表达式的等号是否合法/in 中缀表达式int Judge(

13、char *s) If(等号存在且位置无误)return 1;elsereturn 0;四、程序设计与调试分析1、 本程序的编写和调试环境为VC+6.0；2、 使用到的头文件有 #include #include #include #include #include3、 程序所使用的数据结构为栈；在该程序中分为浮点型的数字栈和字符型的运算符栈；4、测试用例输入的表达式为6*(4.3-0.7)/1.2+3.1(3-1)=：输出结果应为75.66输入表达式15/0=输出结果应为：ERROR！ERROR！输入表达式3-2输出结果应为：表达式无结束符“=”或结束符位置不合法!输入表达式3=2/输出结果

14、应为：表达式无结束符“=”或结束符位置不合法!5、 用户手册1、 进入程序后即显示提示信息：“请输入算术表达式，以=结束”以等待用户输入待求表达式，直到输入“=”为止，如”5*(7.1-8)(4.3+1)/3.1=”该程序仅仅能够满足加减乘除和乘方运算，若用户输入的表达是不合法，或表达式包括程序不满足的运算时，程序报错或无法运行，程序结束；2、 在用户正确输入表达式后，程序会自动将中缀表达式转换为后缀表达式并输出“转化后的后缀表达式为：xxxxxxxx”，然后自动转换为后缀表达式，计算表达式的值并输出中间结果“表达式=结果”和最终结果“The final result is:原表达式=结果”；

15、3、 最终结果输出后，又有提示信息：“你想继续吗？Y或y为继续，其余为退出程序”，以等待用户输入是否继续运行本程序的命令符，若输入“y”或“Y”，则程序自动再次运行，重复2，3步，若输入其它，程序结束。4、 本程序只对实数的加减乘除乘方运算进行求值，且只对“（）”这种形式的括号进行识别，“”或“”都不予以识别，但是”( )”是可以嵌套的，表达式输入完后一定要加“=”表示输入结束，否则程序出错。6、 测试成果1、操作提示2、 表达式计算输入的表达式为6*(4.3-0.7)/1.2+3.1(3-1)=3、 表达式错误时输入表达式15/0=4. 表达式包含不合法字符：5. 输入表达式无结束符“=”或

16、结束符位置不合法(1)表达式无结束符“=”(2) 结束符位置不合法七、源程序清单#include#include#include#include#include#define INIT_SIZE 100 /初始分配最大空间量#define STACKINCREMENT 10 /（默认）增补空间量/数字栈typedef structfloat *base; float *top; int stacksize;Stack_f; /操作符栈typedef structchar *base; char *top; int stacksize; Stack_c;int Judge(char *s);in

17、t InitStack_f(Stack_f *s);int InitStack_c(Stack_c *s);int GetTop_f(Stack_f *s,float *e);int GetTop_c(Stack_c *s,char *e);int Push_f(Stack_f *s,float e);int Push_c(Stack_c *s,char e);int Pop_f(Stack_f *s,float *e);int Pop_c(Stack_c *s,char *e);int precede(char Top_char,char s1_char);int Translate(cha

18、r *s1);int Calculate(Stack_f *s,char *s2);void result(Stack_f *s,char *str);int main()Stack_f stack;char str200;char strk200;char c=Y;while(c=y | c=Y)printf( |-|n);printf( | 表达式求值 |n);printf( |-程序支持实数的加减乘除乘方运算-|n); printf( | 请输入算术表达式,以=结束 |n);printf( |-|n); gets(str);strcpy(strk,str);if(!Judge(str)p

19、rintf(表达式无结束符“=”或结束符位置不合法!n);else if(InitStack_f(&stack)if(Translate(str)printf(转化后的后缀表达式为：n); puts(str);if(Calculate(&stack,str)result(&stack,strk);elseprintf(ERROR !n);elseprintf(ERROR !n);elseprintf(ERROR !n); printf(你想继续吗？Y或y为继续，其余任意键退出。n); c=getchar();getchar();/吞噬掉输入判断符后的nreturn 0;/构造一个存储实型的空栈

20、，预设空间为100，分配失败就退出/return 1:初始化成功 return 0 :初始化失败int InitStack_f(Stack_f *s)s-base=(float *)malloc(INIT_SIZE*sizeof(float);if(s-base)s-top=s-base;s-stacksize=INIT_SIZE; return 1;else return 0;/构造一个存储字符型的空栈,预设空间为100,分配失败就退出/return 1:初始化成功 return 0 :初始化失败int InitStack_c(Stack_c *s)s-base=(char *)malloc

21、(INIT_SIZE*sizeof(char);if(s-base)s-top=s-base;s-stacksize=INIT_SIZE;return 1;else return 0;/若栈s不空，则以e带值返栈顶元素，否则显示错误ERROR,并退出程序/return 1:获取成功 return 0 :获取失败/in Stack_f *s/out float *eint GetTop_f(Stack_f *s,float *e)if(s-top!=s-base)*e=*(s-top-1);return 1;elseprintf(ERROR!);return 0;/取栈顶，若栈s不空，则删除栈s

22、的栈顶元素，用e带值返回，否则退出程序/return 1:获取成功 return 0 :获取失败/in Stack_c *s/out char *eint GetTop_c(Stack_c *s,char *e)if(s-top!=s-base)*e=*(s-top-1);return 1;elseprintf(ERROR!n);return 0;/判断表达式的等号是否合法/in 中缀表达式int Judge(char *s)int len=strlen(s);int j;for(j=0;jtop-s-base=s-stacksize)s-base=(float *)realloc(s-bas

23、e,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)printf(溢出啦!n);return 0;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;return 1;/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间/return 1:压入成功 return 0 :压入失败/in char eint Push_c(Stack_c *s,char e)if(s-top-s-base=s-stacksize)s-base=(char *)reall

24、oc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base)printf(栈满，溢出n);return 0;s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;return 1;/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序/return 1:弹出成功 return 0 :弹出失败/in Stack_f *s/out float *eint Pop_f(Stack_f *s,float *e)if(s-top=s-base)return 0

25、;*e=*-s-top;return 1;/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序/return 1:弹出成功 return 0 :弹出失败/in Stack_c *s/out char *eint Pop_c(Stack_c *s,char *e)if(s-top=s-base)return 0;*e=*-s-top;return 1;/比较运算符的优先级/in char Top_char,char s1_char/return 1:栈顶运算符优先级大于刚读入的运算符；/return 0:栈顶运算符优先级小于刚读入的运算符int precede(char Top_cha

26、r,char s1_char)int i=0,j=0; static char array88=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,)return 1;elsereturn 0;/中缀表达式转换为后缀表达式/in 中缀表达式/out 后缀表达式/return 1转换成功return 0转换失败int Translate(char *s1) char s280;Stack_c Optr;int i=0,j=0;char t;InitStack_c(&Opt

27、r);Push_c(&Optr,();while(s1i!=)if(s1i=0 & s1i=9 | s1i=.) s2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) case(:Push_c(&Optr,s1i);break; case):Pop_c(&Optr,&t); break; while(t!=() s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)Pop_c(&Optr,&t);s2j+=t;Push_c(&Optr,s1i)

28、;i+;Pop_c(&Optr,&t);/表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!=() s2j+=t;Pop_c(&Optr,&t);for(i=0;i=0 & s2i0) m/=10;j-;i+; Push_f(s,m); GetTop_f(s,&m); printf(get:%gn,m);else Pop_f(s,&x);Pop_f(s,&y);switch(s2i)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈case +:z=y+x;printf(%g+%g=%gn,y,x,z);break;case -:z=y-x;printf(

29、%g-%g=%gn,y,x,z);break;case *:z=y*x;printf(%g*%g=%gn,y,x,z);break;case /:if(x=0) printf(ERROR !n); return 0; elsez=y/x;printf(%g/%g=%gn,y,x,z);break; case :z=pow(y,x);printf(%g%g=%gn,y,x,z);break;default:printf(符号不合法!n); return 0; Push_f(s,z);i+;return 1;/写出最终结果/in中缀表达式，数字栈/out中缀表达式=最终结果void result(

30、Stack_f *s,char *str)float v;GetTop_f(s,&v);printf(The final result is:%s%gn,str,v);4.课程设计心得经过两个礼拜以来的艰辛努力，终于完成了本次课程设计的要求。一路走来，程序从一开始的漏洞百出，毫无章法到现在的有板有眼运行流畅。我一步步见证着这个程序的成长，其实对我来说，是一个很焦急到开心的过程。本次的数据结构课程设计，老师对完成设计的质量要求很高，按照软件开发的流程来完成这一份课程设计，对于要完成的任务细化到了每一天。从需求分析，概要设计，详细设计到后期的程序编码，并且每一部分任务在实验报告上都有体现，而且，为了能够实现让使用者轻松使用的效果，也添加了用户手册的部分，而这些恰恰是软件开发过程的一个缩影。数据结构是指相互之间存在一种或多种特定关系的数据元素的组合，当然也是计算机专业的必修专业基础课程。在一开学的时候就了解了这门课程的重要性，所以从那时起我就决定要好好学习这门课程，夯实自己的基础。在此次课程设计中，在一开始选定表达式求值这个题目时，我就了解这是需要运用栈的先进后出的特