表达式求值试验报告

1、阅读使人充实，会谈使人敏捷，写作使人精确。淮海 工学院 计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称： 表达式求值姓 名：学 号：_专业班级：系（院）：计算机工程学院设计时间：设计地点：软件工程实验室、教室成绩:指导教师评语:签名:有勇气承担命运这才是英雄好汉1 .课程设计目的*= 一 «= 一 一 一 一 « 一 9:B » WB HTB »1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程 序求解指定问题。2 .初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3 .提高综合运

2、用所学的理论知识和方法独立分析和解决问题的能力；4 .训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2.课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构 的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一

3、定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用 C/C+,程序书写规范，源程序需加必要的注释；4、每位同学需提交可独立运行的程序；5、每位同学需独立提

4、交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。3.课程设计说明书 >9 J. SI 9. ! X U & II. . )_ IE >. ! , J ). U I一需求分析问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#"，如：# (7+15) * (23-28/4 ) #。引入表达式起始、结束符是为了方便。编程

5、利用“算符优先法”求算 术表达式的值。 基本要求(1)从键盘读入一个合法的算术表达式，输出正确的结果。(2)显示输入序列和栈的变化过程。二概要设计1、设定“操作数”的栈的抽象数据类型定义：ADT SqStack_f数据对象：D=ajaiR,i N数据关系：R1=< ai, ai 1 >| ai 1, ai D ,i=2,n约定an端为栈顶，ai端为栈底。基本操作：InitStack_f(&S)操作结果：构造一个空栈SoGetTop_f(&S,&e)初始条件：栈S已存在。操作结果：用e返回S的栈顶元素。Push_f(&S , ch)初始条件：栈S已存在

6、。操作结果：寸1入元素 ch为新的栈顶元素。Pop_f(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。ADT SqStack_f2、设定“操作符”的栈的抽象数据类型定义：ADT SqStack_c数据对象：D=ajai *''/MA' ,i N 数据关系:R1=< ai, ai 1 >| ai 1, ai D ,i=2,n约定an端为栈顶，ai端为栈底。基本操作:InitStack c(&S)操作结果：构造一个空栈 SoGetTop_c(&S,&e)初始条件：栈S已存在。操作结果：用e返

7、回S的栈顶元素。Push_c(&S, ch)初始条件：栈S已存在。操作结果：寸1入元素 ch为新的栈顶元素。Pop_c(&S,&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。ADT SqStack_c3、本程序包含六个模块1)主程序模块void main()初始化；while(命令="继续")接受数据；处理数据；接受命令；2)栈模块一一实现栈抽象数据类型3判断运算符优先级模块一一判断运算符的优先级别4)后缀表达式转换模块一一将中缀表达式转换为后缀表达式，方便操作5)无括号表示式求值运算模块一一根据后缀表达式求值，并输出中间和最

8、终结果6)运算结果输出模块一一以正确形式输出表达式的值三详细设计1、主程序中需要的全程量#define TTACK_INIT_SIZE 100初始分配最大空间量#define STACKINCREMENT 10/ (默认)增补空间量2、结点类型、指针类型typedef struct float *base; 存储实型数据元素的一位数组float *top; 栈顶指针int stacksize; 栈数组容量SqStack_f;有序存储实型的顺序表类型typedef struct char *base; 存储字符数据元素的一位数组char *top; 栈顶指针int stacksize; 栈数组容

9、量SqStack_c;有序存储字符型的顺序表类型void InitStack_f(SqStack_f *s)void InitStack f(SqStack f *s)力百适二不存福咳渔厂(李将也T的圣移面筏比面为”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的

10、栈顶插入新的栈顶元素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->to

11、p=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->

12、;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带值返回，否则退出

13、程序if(s->top=s->base) exit(1);*e=*-s->top;3、判断运算符优先级的算法:算符间的优先关系如下:+-*/()#+>=<<<<>>->>=<<<>>*>>>=><>>/>>>>=<>>(<<<<<=)>>>>>>#<<<<<=伪码算法：int precede(char Top_cha

14、r,char s1_char)栈顶的运算符赋给Top_char,新读入的运算符赋给s1_char。判断它们的优先级若栈顶运算符优先级高，则返回 1,否则返回0int i,pre2;char op2;op0=Top_char; 栈顶的运算符赋给 op0op1=s1_char; 新读入的运算符赋给op1for (i=0;i<2;i+)switch (opi) case'(':case')':prei=0; break ; 将括号的优先级设为0case'+': case'-':prei=1; break ;/将 + -运算符的优先

15、级设为1case'*': case'/':prei=2; break; 将* / 运算符的优先级设为 2 case'A':prei=3; break; 将人运算符的优先级设为 3 if (pre0>=pre1)栈顶元素优先级高返回1return 1; elsereturn 0;否则返回04、中缀表达式转换为后缀表达式的算法：算法过程描述：1)首先将左括号“(”压进栈，作为栈底元素；2)从左而右对算数表达式进行扫描，每次读入一个字符s1i;3)若遇到数字或小数点，则立即写入 s2i,若遇算数运算符，将“”(空格)写入s2i;4)遇到左括号“(

16、”则压栈；5)若遇算术运算符，如果它们的优先级比栈顶元素高，则直接进栈，否则弹出栈顶元素输出到 s2i,直到新栈顶元素的优先级比它低，然后将它压栈；6)若遇到右括号“)”，则将栈顶元素输出到s2i,直到栈顶元素为“(”，然后相互抵消；7)当扫描到“ #"符号，表明表达式串已全部输入，将栈中的运算符全部输出到s2i,并删除栈顶元素。伪码算法：void Translate(char *s1) 中缀表达式转换为后缀表达式 char s280;SqStack_c Optr; int i=0,j=0; chart;InitStack_c(&Optr);初始化一个存储字符型的空栈，便于存

17、储运算符Push_c(&Optr,'(');首先将左括号“(”压进栈，作为栈底元素 while (s1i!='#')当扫描到的不是“ #"，即表达式串没结束时 if (s1i>='0' && s1i<='9' | s1i='.') 若果是数字或小数点则将其输出给s2is2j+=s1i;if (s1i+1<'0' | s1i+1>'9') && s1i+1!='.') s2j+=''

18、; else switch( s1i) 扫描至ij的是运算符 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

19、,s1i) /遇到算数运算符则比较优先级Pop_c(&Optr,&t);/栈顶元素优先级高，则弹出到 s2i s2j+=t; Push_c(&Optr,s1i);/栈顶元素优先级低，直接压栈 i+; Pop_c(&Optr,&t);while (t!='(') 表达式串已结束，栈中的运算符全部输出到s2i,并删除栈顶元素s2j+=t；Pop_c(&Optr,&t);for(i=0;i<j;i+) 将 s2 复制给 sis1i=s2i;s1i= '#'s1i+1='0'为了方便打印后缀表

20、达式，在字符串结尾加0'5、表示式求值运算的算法：算法描述：1)读入无括号的后缀表达式；2)若为数值和小数点则将其联合转换为浮点型后进栈(存放操作数)；3)若为运算符，让栈顶元素和次顶元素与次运算符进行相应的运算，运算结果打印并进栈；4)重复2) 3)步骤，直到输入为“#"，则此时栈中的结果便是所追求的表达式的值。数值转换为实数的算法描述：1)若为数字，则将其减去0'的ASCII码后就得到该数的数值，并暂存于一个变量m上；2)若继续为数字，也将其减去0'的ASCII码后就得到该数的数值，并将其值加上已存的m*10后的值再存于m；3)重复2)步骤直到遇到小数点，

21、从小数点后的数开始，在重复2)步骤的通知，也记下小数点后的位数n;4)当遇到“ ”(空格)后，即表示此轮需转换的数已读入完毕，则将 m除以10的你次方，则 此时的之记为转换后的实数。伪码算法：void Calculate(SqStack_f *s, char *s2)float m,x,y,z;int i=0,j=0;while (s2i!='#')/读入后缀表达式直到“ #"符号为止 if (s2i>='0 && s2i<='9' | s2i='.') /若为数值和小数点则将其联合转换为浮点型后进栈

22、/数值转换为实数m=0;while (s2i!=' ' && s2i!='.') / 读入的只为数字m=m*10+(float)(s2i+-'0'); 转换为十进制的整数if(s2i='.')/遇到小数点后 j=0；i+；while (s2i!=' ') m=m*10+(float)(s2i+-'0'); 转换为十进制的整数 j+; /记录小数点后的位数 while (j>0) /转换为实数 m/=10;j-; i+； Push_f(s,m); GetTop_f(s,&

23、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 '*

24、':z=y*x;printf("The result is:%gn",z) ;break ; case '/':if (x=0)/报错功能printf("表达式出错，除数为0',无意义n"); exit(1); else z=y/x;printf("The result is:%gn",z);break;case w：z=1; for (j=1;j<=x;j+) /乘方的运算 z=z*y;printf("The result is:%gn",z); Push_f(s,z); i

25、+；6、结果输出的伪码算法： void result(SqStack_f *s) float v;GetTop_f(s,&v);printf("The final result is:%gn",v);/以合适的形式输出结果，省去不必要的小数点阅读使人充实，会谈使人敏捷，写作使人精确。 _ " - - -1一, i 一一,- i - 1 1 "- i- - i 1 - - i-1 - -7、主程序的伪码算法：void main()SqStack_f stack;char str80,c='Y' while(c='y'

26、 | c='Y')/判断是否继续本程序printf("请输入算术表达式本程序支持实数的加减乘除乘方运算,结束前请输入#号！ n")；gets(str);输入表达式InitStack_f(&stack);/初始化一个存储运算结果(实型)的栈Translate(str);调用“中缀表达式转换为后缀表达式函数”printf("转化后的后缀表达式为：n");检验后缀表达式是否转换正确puts(str);/输出后缀表达式Calculate(&stack,str);/计算无括号表达式的值result(&stack);/调用“结

27、果输出函数”printf("你想继续吗？ Y'或'y'为继续，其余为退出程序n");增加程序的连续输入功能c=getchar();getchar();/吞噬掉输入判断符后的n' 四设计与调试分析1、在编程过程中，为了增加程序的实用性，将程序适用范围扩大到了实数型，并增加了连续输入功 能；2、在编程过程中，为了增加程序的健壮性，在运算除法时，考虑到除数为“0”时的报错和及时退出；3、在调试过程中，最初一下子出来程序就出错，为了方便检查错误，故在主函数中增加了检查后缀 表达式是否转换正确的函数，并在每一步计算都跟踪结果是否正确；4、从程序实验题的

28、编制过程中容易看出，线性表的广泛应用，特别是顺序存储结构的栈的应用。本 题中涉及两元素类型(字符型和浮点型)的栈，由于是面向过程的语言，故只能分别定义。五用户手册1、本程序的运行环境为 Windows7旗舰版操作系统，执行文件为：算术表达式求值.exe;2、进入程序后即显示提示信息：“请输入算术表达式，以#'结束”以等待用户输入待求表达式，直到输入“ #"为止，若用户输入的表达式为一个空字符串，则显示 ERROR,程序结束；3、在用户正确输入表达式后，程序会自动将其转换为后缀表达式并输出“转化后的后缀表达式 为:xxxxxxxx ”,然后自动计算表达式的值并输出中间结果“ T

29、he result is: xxxxx”和最终结 果 “The final result is:xxxx ”;4、最终结果输出后，又有提示信息：“你想继续吗？ Y'或'y'为继续，其余为退出程序”，以等待用户输入是否继续运行本程序的命令符，若输入" y”或" Y”，则程序自动再次运行，重复 2, 3步，若输入其它，程序结束。5、本程序只对实数的加减乘除乘方运算进行求值，且只对“()”这种形式的括号进行识别，“>或“口”都不予以识别，表达式输入完后一定要加“#表示输入结束。六测试成果有勇气承担命运这才是英雄好汉阅读使人充实，会谈使人敏捷，写作使人

30、精确。1、程序主界面2、输入正确的表达式输入10* (4.8/4+3人2-5) #,会打印出该式的后缀表达式，并求出最终结果当进行完一次运算后，输入 Y或y会继续进行下一次运算 3、输入除数为0的表达式输入10* (2.7/ (3人2-9) -1) #后，会提示除数为 0,无意义4、输入错误的格式输入15+a#后，会提示ERROR并退出程序七附录（源程序清单）#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define TTACK_INIT_SIZE 100初始分配最大空间量#define STAC

31、KINCREMENT 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 *)mall

32、oc(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;v

33、oid 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);voi

34、d 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+

35、=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->

36、;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_cha

37、r,char s1_char)栈顶的运算符赋给Top_char,新读入的运算符赋给s1_char。判断它们的优先级若栈顶运算符优先级高，则返回 1,否则返回0int i,pre2;char op2;op0=Top_char; /栈顶的运算符赋给op0op1=s1_char; 新读入的运算符赋给op1for(i=0;i<2;i+)switch(opi)case'(':case')':prei=0;break; / 将括号的优先级设为0case'+':case'-':prei=1;break; 将+ -运算符的优先级设为1cas

38、e'*':case7':prei=2;break;/ 将* / 运算符的优先级设为2case'A':prei=3;break;将人运算符的优先级设为 3 if(pre0>=pre1)/栈顶元素优先级高返回1return 1;elsereturn 0;否则返回0void Translate(char *s1) /中缀表达式转换为后缀表达式char s280;SqStack_c Optr;有勇气承担命运这才是英雄好汉阅读使人充实，会谈使人敏捷，写作使人精确。 11 ii-ii 1 lie ii-I 一， 1 lie Il ii1 ' 1 >

39、;> 11 Il ii >_ 1 >> 11 I 1 >> lie-11 I 1 lie-11 ill >> 1 IIl i _ 11 - int i=0,j=0;chart;InitStack_c(&Optr);初始化一个存储字符型的空栈，便于存储运算符Push_c(&Optr,'(');首先将左括号"("压进栈，作为栈底元素 while(s1i!='#') 当扫描到的不是"探,即表达式串没结束时 if(s1i>='0' && s

40、1i<='9' | s1i='.') /若结果是数字或小数点则将其输出给s2is2j+=s1i;if(s1i+1<'0' | s1i+1>'9') && s1i+1!='.') s2j+='' elseswitch(s1i)/扫描到的是运算符 case'(':Push_c(&Optr,s1i);break; 遇到左括号"("则压栈 case')':Pop_c(&Optr,&t);/若遇到右括

41、号")"，则将栈顶元素输出到s2iwhile(t!='(') 直到栈顶元素为"("，然后相互抵消 s2j+=t;Pop_c(&Optr,&t); break;default:while(GetTop_c(&Optr,&t),precede(t,s1i)/遇到算数运算符则比较优先级Pop_c(&Optr,&t);/栈顶元素优先级高，则弹出到 s2i s2j+=t; Push_c(&Optr,s1i);栈顶元素优先级低，直接压栈 有勇气承担命运这才是英雄好汉阅读使人充实，会谈使人敏捷，写

42、作使人精确。i+；Pop_c(&Optr,&t);while(t!='(') 表达式串已结束，栈中的运算符全部输出到s2i,并删除栈顶元素s2j+=t;Pop_c(&Optr,&t);for(i=0;i<j;i+)/ 将 s2 复制给 sis1i=s2i;s1i= '#'s1i+1='0'为了方便打印后缀表达式，在字符串结尾加'0'void Calculate(SqStack_f *s,char *s2)float m,x,y,z;int i=0,j=0;while(s2i!='#&#

43、39;)读入后缀表达式直到"#"符号为止if(s2i>='0' && s2i<='9' | s2i='.') /若为数值和小数点则将其联合转换为浮点型后进栈/数值转换为实数m=0;while(s2i!=' ' && s2i!='.') /读入的只为数字m=m*10+(float)(s2i+-'0'); 转换为十进制的整数if(s2i='.')遇到小数点后 j=0；i+；while(s2i!='')m=m*

44、10+(float)(s2i+-'0'); 转换为十进制的整数j+; 记录小数点后的位数while(j>0) /转换为实数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

45、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 7':if(x=0)/报错功能printf("表达式出错，除数为0',无意义n");exit(1);elsez=y/x;printf("The result is:%gn",z);break;case 'A':z=1;for(j=1;j<=x;j+)乘方的运算z=z*y;printf("The result is:%g