淮海工学院数据结构课程设计表达式求值

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

2、生的理论知识，提 高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2. 课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严 蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、 数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。所选课题：表达式求值问题描述：一个算术表达式是由操作数 （operand）、运算符（operator）和界限符（delimiter） 组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达 式结束符“ =”，口：（

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

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

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

6、_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)/ int Pop_c(Stack_c *s,char *e)/3、系统中的子程序和功能说明：/比较运算符的优先级i=1,2,3,， n，n> 1 且 n 属于整数 D, i=2、n；初始化数字栈 初始化运算符栈数字入栈运算符入栈数字取栈顶元素运

7、算符取栈顶元素弹出栈顶数字元素，e带值返回弹出栈顶运算符元素，e带值返回int precede(char Top_char,char s1_char);/将中缀表达式转化为后缀表达式 int Tran slate(char *s1);/计算过程int Calculate(Stack_f *s,char *s2);/输出计算结果void result(Stack_f *s,char *str);/判断等号是否存在或有误 int Judge(char *s);运算符的优先级转化为后缀表达式计算中缀表达式的值压 入 运 算 符 栈弹出数字初始数字栈取数字栈顶压入数字栈压入运算符栈SC三、详细设计1、

8、基本参数类型的设计(1)/*定义运算符类型栈*/typedef struct char *base; / char *top; / int stacksize; /存储字符数据元素的一维数组 栈顶指针栈数组容量Stack_c; /*定义运算数字类型栈有序存储字符型的顺序表类型*/*定义整型栈*/typedef struct float *base; / float *top; / int stacksize; /存储实型数据元素的一维数组 栈顶指针栈数组容量Stack_f; II 有序存储实型的顺序表类型 2/构造一个存储实型的空栈，预设空间为100，分配失败就退出/return 1:初始化成

9、功 return 0 :初始化失败int In itStack_f(Stack_f *s);分配指定的空间；if(分配成功)初始化栈顶元素；初始化栈的容量；return 1;elsereturn 0;II构造一个存储字符型的空栈，预设空间为100,分配失败就退出/return 1:初始化成功 return 0 :初始化失败int InitStack_c(Stack_c *s)分配指定的空间；if(分配成功)初始化栈顶元素；初始化栈的容量；return 1;elsereturn 0;/若栈s不空，则以e带值返栈顶元素，否则显示错误"ERROR",并退出程序/return 1:

10、获取成功 return 0 :获取失败/in Stack_f *s/out float *eint GetTop f（Stack f *s,float *e）if（栈不为空）*e=栈顶元素；return 1;else报错；return 0;/取栈顶，若栈s不空，则删除栈s的栈顶元素，用e带值返回，否则退出程序/in Stack_c *s/out char *e/return 1:获取成功 return 0 :获取失败int GetTop_f（ Stack_f *s,char *e）if（栈不为空）*e=栈顶元素；return 1;else报错；return 0;/在s的栈顶插入新的栈顶元素e，

11、若栈的当前空间已满，则追加存储空间/in float e/return 1:压入成功 return 0 :压入失败int Push_f（ Stack_f *s,float e）if（栈满）增加数字栈的储存空间；if（增加失败）printf（"栈满，溢出 n"）;return 0;重置栈顶指针；重置栈的容量；压入元素；return 1;/在s的栈顶插入新的栈顶元素e,若栈的当前空间已满，则追加存储空间/in char e/return 1:压入成功 return 0 :压入失败int Push_c（ Stack_c *s,char e）if（栈满）增加运算符栈的储存空间；if

12、（增加失败）printf（”栈满，溢出 n"）;return 0;重置栈顶指针；重置栈的容量；压入元素；return 1;/若栈s不空，则删除栈s的栈顶元素，用 e带值返回，否则退出程序/in Stack_f *s/out float *e/return 1:弹出成功 return 0 :弹出失败int Pop_f（ Stack_f *s,float *e）if（栈为空）return 0;*e=栈顶元素；return 1;/若栈s不空，则删除栈s的栈顶元素，用 e带值返回，否则退出程序/in Stack_c *s/out char *e/return 1:弹出成功 return 0

13、:弹出失败int Pop_c（ Stack_c *s,char *e）if（栈为空）return 0;*e=栈顶元素；return 1;/比较运算符的优先级/in char Top char,char s1 char/return刁:栈顶运算符优先级天于刚读入的运算符7/return 0:栈顶运算符优先级小于刚读入的运算符int precede( char Top_char,char s1_char)int i=O,j=O;/储存各个运算符优先级的比较结果static char array88=>'5'>'5'<'5'<&

14、#39;5'<','<'1'>'5'>5>'5'>'5'<'5'<'5'<','<'1'>'5'>5>'5'>'5'>'5'>'5'<','<'1 5'>'5'>'>'5'

15、;>'5'>'5'>'5'<','<'1 5'>'5'>'>'5'>'5'>'5'>'5'<','<'1 5'>'5'>'<'5'<'5'<'5'<'5'<','<

16、9;1 5一 5'!'>'5'>'5'>'5'>'5'<','!'1，'>'5'>'5<''<''<''<''<''<''!'/确定运算符的优先级switch(Top_char)/ i 为下面array的横标 case '+' : i=O;break;case &#

17、39;-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case 'A' : 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 '*'

18、; : j=2;break;case '/' : j=3;break;case 'A' : j=4;break;case '(' : j=5;break;case ')' : j=6;break;case '=' : j=7;break;返回优先级比较结果/中缀表达式转换为后缀表达式/in中缀表达式/out后缀表达式/return 1 转换成功return 0转换失败int Tran slate(char *s1)char s280;Stack_c Optr;int i=0,j=0;char t;初始化运算符栈Op

19、tr;Push_c(&Optr,'(');while(s1i!='=')if(s1i是数字或小数点的字符)s2j+=s1i;if(s1i不是数字或小数点的字符)s2j+=空格；elseswitch(s1i)case'(': 将s1i压入运算符站;break;case')':弹出运算符栈栈顶元素，将该元素赋值给t; break;while(t!='(')s2j+=t;弹出运算符栈栈顶元素，将该元素赋值给t;break;default:while(取字符站栈顶元素，若优先级大于读入的运算符)弹出栈顶元素并赋值给

20、t;s2j+=t;将t压入运算符栈；i+;弹出栈顶元素并赋值给t;表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!='(')s2j+=t;弹出栈顶元素并赋值给t;将s2重新赋值给s1；s1i= '='sii+i=-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(若为数值和小数点)则将其

21、联合转换为浮点型后进栈；else弹出数字栈栈顶元素弹出数字栈栈顶元素switch(s2i)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈 case '+':z=y+x;输出y+x=z;break;case '-':z=y-x;输出y-x=z;break;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

22、);输出 yx=z;break;default:输出符号不合法!;return 0;将运算结果压入数字栈栈顶;i+；return 1;/写出最终结果/in中缀表达式，数字栈/out中缀表达式=最终结果void result(Stack_f *s,char *str) 取数字栈栈顶；输出最终结果；/判断表达式的等号是否合法/in中缀表达式int Judge(char *s)If(等号存在且位置无误)return 1;elsereturn 0;四、程序设计与调试分析1、 本程序的编写和调试环境为VC+6.0 ；2、使用到的头文件有#in clude<stdio.h>#in clude&

23、lt;stdlib.h>#in clude<malloc.h>#in clude<stri ng.h> #in clude<math.h>3、程序所使用的数据结构为栈；在该程序中分为浮点型的数字栈和字符型的运算符栈；4、测试用例 输入的表达式为6*(4.3-0.7)/1.2+3.1人(3-1)=:输出结果应为 75.66 输入表达式 15/0=输出结果应为：ERROR ！ ERROR ！ 输入表达式3-2输出结果应为：表达式无结束符"=”或结束符位置不合法！ 输入表达式3=2/输出结果应为：表达式无结束符"=”或结束符位置不合法！五

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

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

26、 2+3. 1" (3-1)二转化后的后缀表达式为：6 4, 3 0. 7 L2 /3. 1 3 1 "+二get.: 6get: 4. 3get :O. 1get: 1. 2a 7/L 2=0. 583333get: 3. 1gGt: 3get: 131-33. 1+3=6. 1The final result is:6+ (4, 3-0.7)/1. 2+3.1 (3-1)二6.1 |你想继续吗？Y或、，为继续，其余任意键退出。°3、表达式错误时输入表达式15/0=15/0=转化后的后缀表达式为：15 0 /=get:15目 et :0ERROR !ERROR

27、!你想继续吗？ 丫或为继续，其余任意键退出。V c4.表达式包含不合法字符:3_a=转化后的后缀表达式为：3 -日二get :3_L 07374e+fl08_3=_l* 07374e008符号不合法！ERROR !你想継续吗？'Y或、为缔续，其余任盍键退出，° o5.输入表达式无结束符“=”或结束符位置不合法(1)表达式无结束符“=”3-2表达式无结束符 7 或结束符位置不合法！ 你想继续吗或为继续，其余任意键退出(2)结束符位置不合法筋眨式无结束符7或结束符位置不合法！ 尔想继续吗？ X，或为继续，具余任意键退出。七、源程序清单#i nclude<stdio.h>

28、;#i nclude<stdlib.h>#i nclude<malloc.h>#i ncludevstri ng.h>#in clude<math.h>#defi ne 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(

29、char *s);int In itStack_f(Stack_f *s);int In itStack_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

30、Tran slate(char *s1);int Calculate(Stack_f *s,char *s2);void result(Stack_f *s,char *str);int mai n()Stack_f stack;char str200;char strk200;char c='Y'while(c='y' | c='Y')printf("|n");prin tf("|表达式求值|n");prin tf("|程序支持实数的加减乘除乘方运算|n");printf("

31、|请输入算术表达式，以'二'结束|n");printf("|n");gets(str);strcpy(strk,str);if(!Judge(str)printf("表达式无结束符“=”或结束符位置不合法!n");else if(lni tStack_f(& stack)if(Tra nslate(str)printf("转化后的后缀表达式为：n");puts(str);if(Calculate(& stack,str)result(&stack,strk);elseprintf(&q

32、uot;ERROR !n");elseprin tf("ERROR !n");elseprin tf("ERROR !n");printf("你想继续吗？ 'Y'或'y'为继续，其余任意键退出。n"); c=getchar();getchar();吞噬掉输入判断符后的'n'return 0;/构造一个存储实型的空栈，预设空间为100，分配失败就退出/return 1:初始化成功return 0初始化失败int In itStack_f(Stack_f *s)s->base

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

34、>stacksize=INIT_SIZE;return 1;elsereturn 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;elseprin tf("ERROR!");return 0;/取栈顶，若栈s不空，则删除栈s的栈顶元素，

35、用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;elseprin tf("ERROR!n");return 0;判断表达式的等号是否合法/in中缀表达式int Judge(char *s)in t le n=strle n(s);int j;for(j=0;j<le n-1;j+)if(sj='=')r

36、eturn 0;else if(sle n-1='=')return 1;elsereturn 0;在s的栈顶插入新的栈顶元素e,若栈的当前空间已满，则追加存储空间/return 1:压入成功return 0 :压入失败/in float eint Push f(Stack f *s,float e)if(s->top-s->base>=s->stacksize)s->base=(float*)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(float);if(!s->ba

37、se)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*)rea

38、lloc(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

39、_f(Stack_f *s,float *e) 一 一if(s->top=s->base)return 0;*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/r

40、eturn 1:栈顶运算符优先级大于刚读入的运算符；/return 0:栈顶运算符优先级小于刚读入的运算符int precede(char Top_char,char s1_char) 一 一int i=0,j=0;static char array88=>'J'>'J'<'J'<'J'<'!'<'1'>'J'>J>'J'>'J'<'J'<'J'&l

41、t;'!'<'1'>'J'>J>'J'>'J'>'J'>'J'<'!'<'1 J'>'J'>'>'J'>'J'>'J'>'J'<'!'<'1 J'>'J'>'>'J'>&

42、#39;J'>'J'>'J'<'!'<'1 J'>'J'>'<'J'<'J'<'J'<'J'<'!'<'1 J'=' 一 J'!'J>'J'>'J'>'J'>'J'<'!'!'1J'&g

43、t;'J'>'J<''<''<''<''<''<''!''一'switch(Top_char) _/ i为下面array的横标 case '+' : i=0;break;case '-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break; case 'A' : i=4;bre

44、ak;case '(' : i=5;break;case ')' : i=6;break; case '=' : i=7;break; switch(s1_char) 一/ j为下面array的纵标 case '+' : i=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case 'A' : j=4;break;case '(' : j=5;break;ca

45、se ')' : j=6;break;case '=' : j=7;break;if(arrayij='>')return 1;elsereturn 0;中缀表达式转换为后缀表达式/in中缀表达式/out后缀表达式/return 1转换成功return 0转换失败int Tran slate(char *s1)char s280;Stack_c Optr;int i=0,j=0;char t;In itStack_c(&Optr);Push_c(&Optr,'(');while(s1i!='='

46、;)if(s1i>='0' && s1i<=9 | s1i='.')s2j+=s1i;if(s1i+1v'O' | s1i+1>9) && s1i+1!='.')s2j+=''elseswitch(s1i)case'(':Push_c(&Optr,s1i);break; case')':Pop_c(&Optr, &t); break;while(t!='(')s2j+=t;Pop_c(&

47、Optr, &t);break;default:while(GetTop_c(&Optr, &t),precede(t,s1i)Pop_c(&Optr, &t); s2j+=t;Push_c(&Optr,s1i); _i+；Pop_c(&Optr, &t);表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!='(')s2j+=t;Pop_c(&Optr, &t); _for(i=0;i<j;i+)s1i=s2i;s1i= '='s1i+1='0

48、'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(s2i>='0' && s2i<=9 | s2i='.')m=0;while(s2i!=' ' && s2i!='.')m=m*10+(float)(s2i+-&

49、#39;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,&m);prin tf("get:%gn",m);elsePop_f(s, &x);Pop_f(s, &y);switch(s2i)让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进 栈case '+':z=y+x;pri ntf("

50、;%g+%g=%gn",y,x,z);break;case '-':z=y-x;pri ntf("%g-%g=%gn",y,x,z);break;case '*':z=y*x;pri ntf("%g*%g=%gn",y,x,z);break;case 7':if(x=0)printf("ERROR !n");return 0;elsez=y/x;prin tf("%g/%g=%gn",y,x,z);break;case 'A':z=pow(y,x);pri ntf("%gA%g=%gn",y,x,z);break;default:printf("符号不合法!n&q