表达式求值实验报告.doc

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 表达式求值 姓 名： 学 号： 专业班级： 系 （院）： 计算机工程学院 设计时间： 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 22 页，共 21 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1） 从键盘读入一个合法的算术表达式，输出正确的结果。（2） 显示输入序列和栈的变化过程。二 概要设计1、设定“操作数”的栈的抽象数据类型定义：ADT SqStack_f数据对象：D=数据关系：R1=|,i=2,，n约定端为栈顶，端为栈底。基本操作： InitStack_f(&S) 操作结果：构造一个空栈S。 GetTop_f(&S,&e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_f(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_f(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。ADT SqStack_f2、设定“操作符”的栈的抽象数据类型定义：ADT SqStack_c数据对象：D=数据关系：R1=|,i=2,，n约定端为栈顶，端为栈底。基本操作： InitStack_c(&S) 操作结果：构造一个空栈S。 GetTop_c(&S,&e) 初始条件：栈S已存在。 操作结果：用e返回S的栈顶元素。 Push_c(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop_c(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。ADT SqStack_c3、本程序包含六个模块1）主程序模块void main( )初始化；while(命令=“继续”)接受数据；处理数据；接受命令；2）栈模块实现栈抽象数据类型3）判断运算符优先级模块判断运算符的优先级别4）后缀表达式转换模块将中缀表达式转换为后缀表达式，方便操作5）无括号表示式求值运算模块根据后缀表达式求值，并输出中间和最终结果6）运算结果输出模块以正确形式输出表达式的值三 详细设计1、主程序中需要的全程量#define TTACK_INIT_SIZE 100 /初始分配最大空间量#define STACKINCREMENT 10 /（默认）增补空间量2、结点类型、指针类型typedef structfloat *base; /存储实型数据元素的一位数组float *top; /栈顶指针int stacksize; /栈数组容量SqStack_f; /有序存储实型的顺序表类型typedef structchar *base; /存储字符数据元素的一位数组char *top; /栈顶指针int stacksize; /栈数组容量SqStack_c; /有序存储字符型的顺序表类型void InitStack_f(SqStack_f *s)void InitStack_f(SqStack_f *s)/构造一个存储实型（字符型）的空栈，预设空间为100，分配失败就退出void GetTop_f(SqStack_f *s,float *e)void GetTop_c(SqStack_c *s,char *e)/若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序void Push_f(SqStack_f *s,float e)void Push_c(SqStack_c *s,char e)/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间void Pop_f(SqStack_f *s,float *e)void Pop_c(SqStack_c *s,char *e)/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序其中部分操作的伪码算法（由于比较类似，以浮点型的栈为例）void InitStack_f(SqStack_f *s)/构造一个存储实型的空栈，预设空间为100，分配失败就退出s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void GetTop_f(SqStack_f *s,float *e)/若栈s不空，则以e带值返栈顶元素，否则显示错误“ERROR”,并退出程序if(s-top=s-base)printf(ERROR!n);exit(1);*e=*(s-top-1);void Push_f(SqStack_f *s,float e)/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间if(s-top-s-base=s-stacksize)s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)printf(OVERFLOW!n);exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Pop_f(SqStack_f *s,float *e)/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序if(s-top=s-base)exit(1);*e=*-s-top;3、判断运算符优先级的算法：算符间的优先关系如下：+-*/()#+=-=*=/=(#=伪码算法：int precede(char Top_char,char s1_char)/栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。判断它们的优先级 /若栈顶运算符优先级高，则返回1，否则返回0int i,pre2;char op2;op0=Top_char; /栈顶的运算符赋给op0op1=s1_char; /新读入的运算符赋给op1for(i=0;i=pre1) /栈顶元素优先级高返回1return 1;elsereturn 0; /否则返回04、中缀表达式转换为后缀表达式的算法：算法过程描述：1) 首先将左括号“(”压进栈，作为栈底元素；2) 从左而右对算数表达式进行扫描，每次读入一个字符s1i；3) 若遇到数字或小数点，则立即写入s2i，若遇算数运算符，将“ ”（空格）写入s2i；4) 遇到左括号“(”则压栈；5) 若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到s2i，直到新栈顶元素的优先级比它低，然后将它压栈；6) 若遇到右括号“）”，则将栈顶元素输出到s2i，直到栈顶元素为“（”，然后相互抵消；7) 当扫描到“#”符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2i，并删除栈顶元素。伪码算法：void Translate(char *s1) /中缀表达式转换为后缀表达式char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);/初始化一个存储字符型的空栈，便于存储运算符Push_c(&Optr,();/ 首先将左括号“(”压进栈，作为栈底元素while(s1i!=#) /当扫描到的不是“#”，即表达式串没结束时if(s1i=0 & s1i=9 | s1i=.) /若果是数字或小数点则将其输出给s2is2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) /扫描到的是运算符 case(:Push_c(&Optr,s1i);break;/ 遇到左括号“(”则压栈case):Pop_c(&Optr,&t); /若遇到右括号“）”，则将栈顶元素输出到s2iwhile(t!=() /直到栈顶元素为“（”，然后相互抵消s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)/遇到算数运算符则比较优先级Pop_c(&Optr,&t);/栈顶元素优先级高，则弹出到s2is2j+=t;Push_c(&Optr,s1i);/栈顶元素优先级低，直接压栈i+;Pop_c(&Optr,&t);while(t!=() /表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素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(The result is:%gn,m);else /读入的为运算符Pop_f(s,&x);/弹出栈顶元素Pop_f(s,&y);/弹出次顶元素switch(s2i)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈case +:z=y+x;printf(The result is:%gn,z);break;case -:z=y-x;printf(The result is:%gn,z);break;case *:z=y*x;printf(The result is:%gn,z);break;case /:if(x=0) /报错功能 printf(表达式出错，除数为0，无意义n); exit(1); elsez=y/x;printf(The result is:%gn,z);break;case :z=1;for(j=1;j=x;j+) /乘方的运算 z=z*y; printf(The result is:%gn,z); Push_f(s,z);i+;6、结果输出的伪码算法：void result(SqStack_f *s)float v;GetTop_f(s,&v);printf(The final result is:%gn,v);/以合适的形式输出结果，省去不必要的小数点7、主程序的伪码算法：void main()SqStack_f stack;char str80,c=Y;while(c=y | c=Y)/判断是否继续本程序printf(请输入算术表达式本程序支持实数的加减乘除乘方运算，结束前请输入#号！n); gets(str);/输入表达式 InitStack_f(&stack);/初始化一个存储运算结果（实型）的栈 Translate(str);/调用“中缀表达式转换为后缀表达式函数” printf(转化后的后缀表达式为：n);/检验后缀表达式是否转换正确 puts(str);/输出后缀表达式 Calculate(&stack,str);/计算无括号表达式的值 result(&stack);/调用“结果输出函数” printf(你想继续吗？Y或y为继续，其余为退出程序n);/增加程序的连续输入功能 c=getchar();getchar();/吞噬掉输入判断符后的n四 设计与调试分析1、 在编程过程中，为了增加程序的实用性，将程序适用范围扩大到了实数型，并增加了连续输入功能；2、 在编程过程中，为了增加程序的健壮性，在运算除法时，考虑到除数为“0”时的报错和及时退出；3、 在调试过程中，最初一下子出来程序就出错，为了方便检查错误，故在主函数中增加了检查后缀表达式是否转换正确的函数，并在每一步计算都跟踪结果是否正确；4、 从程序实验题的编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的栈的应用。本题中涉及两元素类型（字符型和浮点型）的栈，由于是面向过程的语言，故只能分别定义。五 用户手册1、 本程序的运行环境为Windows7旗舰版操作系统，执行文件为：算术表达式求值.exe；2、 进入程序后即显示提示信息：“请输入算术表达式，以#结束”以等待用户输入待求表达式，直到输入“#”为止，若用户输入的表达式为一个空字符串，则显示ERROR，程序结束；3、 在用户正确输入表达式后，程序会自动将其转换为后缀表达式并输出“转化后的后缀表达式为：xxxxxxxx”，然后自动计算表达式的值并输出中间结果“The result is：xxxxx”和最终结果“The final result is:xxxx”；4、 最终结果输出后，又有提示信息：“你想继续吗？Y或y为继续，其余为退出程序”，以等待用户输入是否继续运行本程序的命令符，若输入“y”或“Y”，则程序自动再次运行，重复2，3步，若输入其它，程序结束。5、 本程序只对实数的加减乘除乘方运算进行求值，且只对“（）”这种形式的括号进行识别，“”或“”都不予以识别，表达式输入完后一定要加“#”表示输入结束。六 测试成果1、程序主界面2、输入正确的表达式输入10*（4.8/4+32-5）#，会打印出该式的后缀表达式，并求出最终结果当进行完一次运算后，输入Y或y会继续进行下一次运算3、输入除数为0的表达式输入10*（2.7/（32-9）-1）#后，会提示除数为0，无意义4、输入错误的格式输入15+a#后，会提示ERROR并退出程序七 附录（源程序清单）#include#include#include#define TTACK_INIT_SIZE 100 /初始分配最大空间量#define STACKINCREMENT 10 /（默认）增补空间量typedef structfloat *base; /存储实型数据元素的一维数组float *top; /栈顶指针int stacksize; /栈数组容量SqStack_f; /有序存储实型的顺序表类型typedef structchar *base; /存储字符数据元素的一维数组char *top; /栈顶指针int stacksize; /栈数组容量SqStack_c; /有序存储字符型的顺序表类型void InitStack_f(SqStack_f *s)/构造一个存储实型的空栈，预设空间为100，分配失败就退出s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void InitStack_c(SqStack_c *s)/构造一个存储字符型的空栈,预设空间为100,分配失败就退出s-base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void GetTop_f(SqStack_f *s,float *e)/若栈s不空，则以e带值返栈顶元素，否则显示错误ERROR,并退出程序if(s-top=s-base)printf(ERROR!n);exit(1);*e=*(s-top-1);void GetTop_c(SqStack_c *s,char *e)/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序if(s-top=s-base)printf(ERROR!n);exit(1);*e=*(s-top-1);void Push_f(SqStack_f *s,float e)/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间if(s-top-s-base=s-stacksize)s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)printf(OVERFLOW!n);exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Push_c(SqStack_c *s,char e)/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间if(s-top-s-base=s-stacksize)s-base=(char *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base)printf(栈满，溢出n);exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Pop_f(SqStack_f *s,float *e)/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序if(s-top=s-base)exit(1);*e=*-s-top;void Pop_c(SqStack_c *s,char *e)/若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序if(s-top=s-base)exit(1);*e=*-s-top;int precede(char Top_char,char s1_char)/栈顶的运算符赋给Top_char，新读入的运算符赋给s1_char。判断它们的优先级 /若栈顶运算符优先级高，则返回1，否则返回0int i,pre2;char op2;op0=Top_char; /栈顶的运算符赋给op0op1=s1_char; /新读入的运算符赋给op1for(i=0;i=pre1) /栈顶元素优先级高返回1return 1;elsereturn 0; /否则返回0void Translate(char *s1) /中缀表达式转换为后缀表达式char s280;SqStack_c Optr;int i=0,j=0;char t;InitStack_c(&Optr);/初始化一个存储字符型的空栈，便于存储运算符Push_c(&Optr,();/ 首先将左括号(压进栈，作为栈底元素while(s1i!=#) /当扫描到的不是#，即表达式串没结束时if(s1i=0 & s1i=9 | s1i=.) /若结果是数字或小数点则将其输出给s2is2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) /扫描到的是运算符 case(:Push_c(&Optr,s1i);break;/ 遇到左括号(则压栈case):Pop_c(&Optr,&t); /若遇到右括号），则将栈顶元素输出到s2iwhile(t!=() /直到栈顶元素为(，然后相互抵消s2j+=t;Pop_c(&Optr,&t);break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)/遇到算数运算符则比较优先级Pop_c(&Optr,&t);/栈顶元素优先级高，则弹出到s2is2j+=t;Push_c(&Optr,s1i);/栈顶元素优先级低，直接压栈i+;Pop_c(&Optr,&t);while(t!=() /表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素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(The result is:%gn,m);else /读入的为运算符Pop_f(s,&x);/弹出栈顶元素Pop_f(s,&y);/弹出次顶元素switch(s2i)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈case +:z=y+x;printf(The result is:%gn,z);break;case -:z=y-x;printf(The result is:%gn,z);break;case *:z=y*x;printf(The result is:%gn,z);break;case /:if(x=0) /报错功能 printf(表达式出错，除数为0，无意义n); exit(1); elsez=y/x;printf(The result is:%gn,z);break;case :z=1;for(j=1;j=x;j+) /乘方的运算 z=z*y; printf(The result is:%gn,z); Push_f(s,z);i+;void result(SqStack_f *s)float v;GetTop_f(s,&v);printf(The final result is:%gn,v);/以合适的形式输出结果，省去不必要的小数点void main()SqStack_f stack;char str80,c=Y;while(c=y | c=Y)/判断是否继续本程序printf(|-|n);printf(| 表达式求值 |n);printf(|-本程序支持实