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

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,ai>|ai-1,aiD，i=2、n；约定an端为栈顶，ai端为栈底2、基本操作及作用(1)初始化栈int InitStack_f(Stack_f *s)/ 初始化数字栈int InitStack_c(Stack_c *s)/ 初始化运算符栈(2)入

6、栈int Push_f(Stack_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)/弹出栈顶运算符元

7、素，e带值返回3、系统中的子程序和功能说明：/比较运算符的优先级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、;>*>>>><<>>/>>>><<>>>>>>><>>（<<<<<<=）>>>><>>=<<<<<<= 计算中缀表达式的值初始运算符栈 后缀表达式初始数字栈 转化为后缀表达式取数字栈顶主程序模块弹出运算符栈 表达式运算符 数字压入数字栈运算符数字弹出数字栈 压入运算符栈栈数字取运算符栈顶 运算符 运算符压入运算符栈运算符 计算结果输

9、出结果 SC图三、详细设计1、 基本参数类型的设计 （1）/* 定义运算符类型栈 */typedef structchar *base; /存储字符数据元素的一维数组char *top; /栈顶指针int stacksize; /栈数组容量Stack_c; /有序存储字符型的顺序表类型/* 定义整型栈 */ /* 定义运算数字类型栈 */typedef structfloat *base; /存储实型数据元素的一维数组float *top; /栈顶指针int stacksize; /栈数组容量Stack_f; /有序存储实型的顺序表类型2/构造一个存储实型的空栈，预设空间为100，分配失败就退

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

11、t;,并退出程序/return 1:获取成功 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

12、;/在s的栈顶插入新的栈顶元素e，若栈的当前空间已满，则追加存储空间/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(栈满)

13、增加运算符栈的储存空间;if(增加失败)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

14、:弹出成功 return 0 :弹出失败int Pop_c(Stack_c *s,char *e)if(栈为空)return 0;*e=栈顶元素;return 1;/比较运算符的优先级/in char Top_char,char s1_char/return 1:栈顶运算符优先级大于刚读入的运算符；/return 0:栈顶运算符优先级小于刚读入的运算符int precede( char Top_char,char s1_char)int i=0,j=0; /储存各个运算符优先级的比较结果static char array88='>', '>', &#

15、39;<', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<'

16、,'<', '>', '>', '>', '>', '>', '>', '<','<', '>', '>','>', '>', '>', '>', '<','<', '>', '>'

17、,'<', '<', '<', '<', '<','<', '=', '!', '>', '>', '>', '>', '<','!', '>', '>', '<', '<', '<', '&

18、lt;', '<','<', '!', '=' /确定运算符的优先级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 ')

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

20、 : 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是数字或小数点的字符) s2j+=s1i;if(s1i不是数字或小数点的字符)s2j+=空格;elseswitch(s1i) case'(':将s1

21、i压入运算符站;break; case')':弹出运算符栈栈顶元素，将该元素赋值给t; break; while(t!='(') s2j+=t;弹出运算符栈栈顶元素，将该元素赋值给t;break;default:while(取字符站栈顶元素，若优先级大于读入的运算符)弹出栈顶元素并赋值给t;s2j+=t;将t压入运算符栈;i+;弹出栈顶元素并赋值给t;表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!='(') s2j+=t;弹出栈顶元素并赋值给t; 将s2重新赋值给s1；s1i= '='s1i+1=&#

22、39;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 '-'

23、: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);输出yx=z;break;default: 输出符号不合法!; return 0; 将运算结果压入数字栈栈顶;i+;return 1;/写出最终结果/in中缀表达式，数字栈/out中缀表达式=最终结果void result(Stack_f *s

24、,char *str) 取数字栈栈顶；输出最终结果；/判断表达式的等号是否合法/in 中缀表达式int Judge(char *s) If(等号存在且位置无误)return 1;elsereturn 0;四、程序设计与调试分析1、 本程序的编写和调试环境为VC+6.0；2、 使用到的头文件有 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #include<math.h>3、 程序所使用的数据结构为栈；在该程序中分为浮点型的数字栈和字

25、符型的运算符栈；4、测试用例输入的表达式为6*(4.3-0.7)/1.2+3.1(3-1)=：输出结果应为75.66输入表达式15/0=输出结果应为：ERROR！ERROR！输入表达式3-2输出结果应为：表达式无结束符“=”或结束符位置不合法!输入表达式3=2/输出结果应为：表达式无结束符“=”或结束符位置不合法!5、 用户手册1、 进入程序后即显示提示信息：“请输入算术表达式，以=结束”以等待用户输入待求表达式，直到输入“=”为止，如”5*(7.1-8)(4.3+1)/3.1=”该程序仅仅能够满足加减乘除和乘方运算，若用户输入的表达是不合法，或表达式包括程序不满足的运算时，程序报错或无法运行

26、，程序结束；2、 在用户正确输入表达式后，程序会自动将中缀表达式转换为后缀表达式并输出“转化后的后缀表达式为：xxxxxxxx”，然后自动转换为后缀表达式，计算表达式的值并输出中间结果“表达式=结果”和最终结果“The final result is:原表达式=结果”；3、 最终结果输出后，又有提示信息：“你想继续吗？'Y'或'y'为继续，其余为退出程序”，以等待用户输入是否继续运行本程序的命令符，若输入“y”或“Y”，则程序自动再次运行，重复2，3步，若输入其它，程序结束。4、 本程序只对实数的加减乘除乘方运算进行求值，且只对“（）”这种形式的括号进行识别，“

27、”或“”都不予以识别，但是”( )”是可以嵌套的，表达式输入完后一定要加“=”表示输入结束，否则程序出错。6、 测试成果1、操作提示2、 表达式计算输入的表达式为6*(4.3-0.7)/1.2+3.1(3-1)=3、 表达式错误时输入表达式15/0=4. 表达式包含不合法字符：5. 输入表达式无结束符“=”或结束符位置不合法(1)表达式无结束符“=”(2) 结束符位置不合法七、源程序清单#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include&l

28、t;math.h>#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);int InitStack_f(Stack_f *s);int InitStack_c(Stack_c *s);int GetTop_f(S

29、tack_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(char *s1);int Calculate(Stack_f *s,char *s2);void result(Stack_f *s,cha

30、r *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);s

31、trcpy(strk,str);if(!Judge(str)printf("表达式无结束符“=”或结束符位置不合法!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("E

32、RROR !n"); printf("你想继续吗？'Y'或'y'为继续，其余任意键退出。n"); c=getchar();getchar();/吞噬掉输入判断符后的'n'return 0;/构造一个存储实型的空栈，预设空间为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->

33、;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(INIT_SIZE*sizeof(char);if(s->base)s->top=s->base;s->stacksize=INIT_SIZE;return 1;else return 0;/若栈s不空，则以e带值返栈顶元素，否则显示错

34、误"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的栈顶元素，用e带值返回，否则退出程序/return 1:获取成功 return 0 :获取失败/in Stack_c *s/out char *eint G

35、etTop_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;j<len-1;j+)if(sj='=')return 0;else if(slen-1='=')return 1;elsereturn 0;/在s的栈顶插入新的栈顶元素e，若栈

36、的当前空间已满，则追加存储空间/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->base)printf("溢出啦!n");return 0;s->top=s->base+s->stacksiz

37、e;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 *)realloc(s->base,(s->stacksize+STACKINCREMENT)*sizeof(char);if(!s->base

38、)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;*e=*-s->top;return

39、 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_char,char

40、 s1_char)int i=0,j=0; static char array88='>', '>', '<', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '<', '>', '>', &#

41、39;>', '>', '>', '>', '<','<', '>', '>', '>', '>', '>', '>', '<','<', '>', '>','>', '>', '>', &

42、#39;>', '<','<', '>', '>','<', '<', '<', '<', '<','<', '=', '!', '>', '>', '>', '>', '<','!', '>&

43、#39;, '>', '<', '<', '<', '<', '<','<', '!', '=' switch(Top_char) / i为下面array的横标 case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; case '/' : i=3;break;case &#

44、39;' : 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 '*' : j=2;break; case '/' : j=3;break;case '' : j=4;break; case '

45、(' : j=5;break; case ')' : j=6;break; case '=' : j=7;break; if(arrayij='>')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(&Optr);Push_c(&Optr,'(&#

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

47、p;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);i+;Pop_c(&Optr,&t);/表达式串已结束，栈中的运算符全部输出到s2i，并删除栈顶元素while(t!='(') s2j+=t;Pop_c(&Optr,&t);for(i=0;i

48、<j;i+) s1i=s2i; 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(s2i>='0' && s2i<='9' | s2i='.')m=0;while(s2

49、i!=' ' && 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,&m); printf("get:%gn",m);else Pop_f(s,&x);Pop_f(s,&y);switch(s2i

50、)/让栈顶和次顶元素与次运算符进行相应的运算，运算结果打印并进栈case '+':z=y+x;printf("%g+%g=%gn",y,x,z);break;case '-':z=y-x;printf("%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