《数据结构》课程设计--表达式求值算法实现.doc

河南工程学院数据结构与算法课程设计成果报告表达式求值算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目表达式求值算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 程序设计思想12 分析与设计22.1 题目分析22.2 算法描述32.3 储存结构设计42.4程序流程图53 程序清单64 测试144.1 测试数据144.2 测试结果分析155 总结16参考文献171 课程设计目标与任务根据课堂讲授的内容，做相应的自主练习，消化课堂所讲解的内容，通过调试典型例题或习题积累调试c程序的经验，通过完成辅助教材中的编程题，逐渐培养学生的编程能力，用计算机解决实际问题的能力。1.1 课程设计目标数据结构课程设计的目标是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练进行复杂程序设计的技能和培养良好的程序设计习惯。1.2 课程设计任务设计表达式的相关函数库，以便在程序设计中调用。对于输入的表示式（涉及加减乘除，带括弧的混合运算），设计程序求表达式的值。最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 程序设计思想任何一个表达式都是有操作数、运算符和界限符组成的，我们称为单词。我们把运算符和界限符统称为操作符。为了实现算符优先，我们可以使用两个工作栈。一个可以用来寄存运算符，另外一个可以用来寄存操作符或者运算结果。首先置操作符栈为空栈表达式起始符为运算符的栈底元素。一次读入每一个字符，若是操作符则进操作符栈，若是运算符则和栈顶运算符比较优先权后作出相应操作，直至整个表达式求值完毕。2 分析与设计我们对程序的分析是很重要的步奏，分析程序的要求可以让我们对程序有一定的框架，让我们可以根据分析更好的设计程序，让我们的设计可以根据对程序的分析一步步来完成对程序的设计。所以程序的分析和设计是不可缺少的一部分。2.1 题目分析利用栈求解表达式的值。题目涉及加减乘除，带括弧的混合运算。要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则。为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果，操作栈op，用于存放。把输入表达式分为两部分数字和操作符分放入两个栈中，符号栈识别符号的优先等级再按照优先等在操作栈中级计算出结果并输出最后的计算结果。实现表达式的求值：要用栈求解一个表达式,就要将这个表达式翻译成正确求值的一个机器指令序列,即正确解释表达式,了解算术四则混合运算的规则：先乘除,后加减;从左算到右;先括号内,后括号外。再根据这个运算优先的规定来实现对表达式的编译或解释执行.任何一个表达式都是由操作数(st)和操作符(op)组成的，根据四则运算基本法则，在运算的每一步中，任意两个相继出现的操作符op1和op2之间的优先关系最多有以下3种：1.op1的优先级低于op22.op1的优先级等于op23.op1的优先级小于op2为实现运算符优先，可以使用两个操作栈，操作栈st,用于存放操作数及运算结果；操作栈op，用于存放操作符。2.2 算法描述1、首先将中缀表达式转换成后缀表达式：(1)从左至右依次扫描中缀表达式的每一个字符，如果是数字字符和“.” ，则直接将它们写入后缀表达式中。(2)如果遇到的是开括号“（”，则将它压入一个操作符栈中，它表明一个新的计算层次的开始，在遇到和它匹配的闭括号时，将栈中元素弹出并放入后缀表达式中，直到栈顶元素为开括号“（”时，将栈顶元素“（”弹出，表明这一层括号内的操作处理完毕。(3)如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： a)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取出栈顶元素放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优先级小于当前操作符的优先级；b)当所遇到的操作符的优先级大于栈顶元素的优先级时，则将它压入栈中。重复上述步骤直到遇到中缀表达式的结束0，弹出栈中的所有元素并放入后缀表达式中，算法结束。2、对后缀表达式求值：将遇到的操作数暂存在一个操作数栈中，凡是遇到操作符，便从栈中弹出两个操作数执行相应的操作，并将结果存于操作数栈中，直到表达式处理完毕，最后压入栈中的数就是表达式的结果。2.3 储存结构设计设计两个栈来分别储存操作数和操作符，这样才能更好的对表达式进行运算符的优先级别分析和运算。所以成语的储存结构是：typedef struct char op; int level; opt; typedef struct opt stMAXLEN; int top; op_stack; typedef struct double DMAXLEN; int top; 2.4程序流程图程序流程图是程序分析中最基础的，最重要的分析技术，它是进行流程程序分析过程中最基本的工具。程序流程图是方法研究改进工作方法的有用工具，不论作业研究过程中运用何种技术，程序流程图总是必须的一步，它是应用最普遍的一种工具。开始输入表达式是符号还是数字表达式结束和OP栈空结果为ST栈顶值结束是当前符号优先级栈顶符号优先级或OP栈空当前符号进OP栈否是出栈几个数字，一个符号进行处理，结果压入ST栈数字否符号进ST栈图2.1 程序流程图3 程序清单#include stdio.h #include string.h #include stdlib.h #define MAXLEN 100 typedef struct char op; int level; opt; typedef struct /定义操作符栈 opt stMAXLEN; int top; op_stack; typedef struct /定义值栈 double DMAXLEN; int top; D_stack; opt peek(op_stack *s) /定义看栈顶函数 opt error=$,-2; if(s-top=0) return s-sts-top; else return error; int IsEmpty(op_stack *s) /定义判断栈空的函数 if(s-topsts-top.op; char push(op_stack *s,opt c) /定义入栈函数 s-top+; s-sts-top=c; return c.op; opt pop(op_stack *s) /定义出栈函数 opt i; opt error=$,-2; if(s-top=0) i=s-sts-top; s-sts-top.op=0; s-top-; return i; else return error; void clear(op_stack *s) /定义初始化栈 s-top=-1; double Dpeek(D_stack *s) /定义看栈顶函数 if(s-top=0) return s-Ds-top; else return 0; int DIsEmpty(D_stack *s) /定义判断栈空的函数 if(s-topDs-top); double Dpush(D_stack *s,double c) /定义入栈函数 s-top+; s-Ds-top=c; return c; double Dpop(D_stack *s) /定义出栈函数 double i; if(s-top=0) i=s-Ds-top; s-Ds-top=0; s-top-; return i; else return 0; void Dclear(D_stack *s) /定义初始化栈 s-top=-1; double calval(char *exp) op_stack os; /定义两个栈 D_stack ds; char tmpMAXLEN=0; int i=0,leng; double dtmp,dpoptmp; opt A=+,1; opt R=-,1; opt M=*,2; opt D=/,2; opt B=(,-1; opt Mo=%,2; clear(&os); Dclear(&ds); while(*exp!=0) while(*exp = 0 & *exp = 0 & *exp = 9 | *exp = .) tmpi+=*exp+; dtmp=atof(tmp); Dpush(&ds,dtmp); leng=strlen(tmp); for(i=0;ileng;i+) tmpi=0; i=0; switch(*exp) case + : if(!IsEmpty(&os) | peek(&os).level =A.level) switch(pop(&os).op) case %: dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,A); *exp+; break; case -: if(!IsEmpty(&os) | peek(&os).level =R.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,R); *exp+; break; case *: if(!IsEmpty(&os) | peek(&os).level =M.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,M); *exp+; break; case /: if(!IsEmpty(&os) | peek(&os).level =D.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,D); *exp+; break; case %: if(!IsEmpty(&os) | peek(&os).level =Mo.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,Mo); *exp+; break; case (: push(&os,B); exp+; break; case ): while(peek(&os).level!=-2) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; pop(&os); /弹出( exp+; break; while(IsEmpty(&os) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; return Dpop(&ds); void main() char stringMAXLEN; char *p=string; printf(输入表达式:n); gets(p); printf(表达式的结果是%s=%fnn,string,calval(p); 4 测试4.1 测试数据输入表达式4+6*(2+3)/2运行结果如图4.1：图4.1 表达式的运行结果输入表达式5*2+3*（2+3）运行结果如图4.2：图4.2 表达式的运行结果输入表达式3*2+4/（3-1）运行结果如图4.3图4.3 表达式的运行结果4.2 测试结果分析第一程序能自动识别和按照四则运算的法则来进行计算先算乘除再算加减并能输出正确运算结果。第二程序能识别括号并进行运算时先计算括号内的再进行括号外的，最后能正确输出的运算结果。5 总结在这一周的实训里，在编写程序的时候遇到了很大的麻烦，需要很多的专业知识，让我明白自己在哪些知识不够了解。在反复的翻阅课本后才对这个题目有了一点头绪。在编写的过程中遇到很多困难，在同学和老师的帮助下终于完成了。这次实训让我明白我有很多的不足，对很多的专业知识不够了解，不过在这次试训中让我巩固很多专业知识和认识了很多新的知识。这次实训让我收获很多。参考文献1严蔚敏等.数据结构（C语言版）.清华大学出版社2朱战立.数据结构（第四版）.电子工业出版社3 吴跃.数据结构和算法.机械工业出版社 4周海英等.数据结构与算法设计（第二版）.国际工业出版社5谭浩强著.C语言设计题解与上机指导.清华大学出版社6谭浩强著.C面向对象程序设计 谭浩强.清华大学出版社 #include stdio.h #include string.h #include stdlib.h #define MAXLEN 100 typedef struct char op; int level; opt; typedef struct /定义操作符栈 opt stMAXLEN; int top; op_stack; typedef struct /定义值栈 double DMAXLEN; int top; D_stack; opt peek(op_stack *s) /定义看栈顶函数 opt error=$,-2; if(s-top=0) return s-sts-top; else return error; int IsEmpty(op_stack *s) /定义判断栈空的函数 if(s-topsts-top.op; char push(op_stack *s,opt c) /定义入栈函数 s-top+; s-sts-top=c; return c.op; opt pop(op_stack *s) /定义出栈函数 opt i; opt error=$,-2; if(s-top=0) i=s-sts-top; s-sts-top.op=0; s-top-; return i; else return error; void clear(op_stack *s) /定义初始化栈 s-top=-1; double Dpeek(D_stack *s) /定义看栈顶函数 if(s-top=0) return s-Ds-top; else return 0; int DIsEmpty(D_stack *s) /定义判断栈空的函数 if(s-topDs-top); double Dpush(D_stack *s,double c) /定义入栈函数 s-top+; s-Ds-top=c; return c; double Dpop(D_stack *s) /定义出栈函数 double i; if(s-top=0) i=s-Ds-top; s-Ds-top=0; s-top-; return i; else return 0; void Dclear(D_stack *s) /定义初始化栈 s-top=-1; double calval(char *exp) op_stack os; /定义两个栈 D_stack ds; char tmpMAXLEN=0; int i=0,leng; double dtmp,dpoptmp; opt A=+,1; opt R=-,1; opt M=*,2; opt D=/,2; opt B=(,-1; opt Mo=%,2; clear(&os); Dclear(&ds); while(*exp!=0) while(*exp = 0 & *exp = 0 & *exp = 9 | *exp = .) tmpi+=*exp+; dtmp=atof(tmp); Dpush(&ds,dtmp); leng=strlen(tmp); for(i=0;ileng;i+) tmpi=0; i=0; switch(*exp) case + : if(!IsEmpty(&os) | peek(&os).level =A.level) switch(pop(&os).op) case %: dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,A); *exp+; break; case -: if(!IsEmpty(&os) | peek(&os).level =R.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; case +: dpoptmp=Dpop(&ds)+Dpop(&ds); Dpush(&ds,dpoptmp); break; case -: dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)-dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,R); *exp+; break; case *: if(!IsEmpty(&os) | peek(&os).level =M.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,M); *exp+; break; case /: if(!IsEmpty(&os) | peek(&os).level =D.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&ds,dpoptmp); break; case / : dpoptmp=Dpop(&ds); dpoptmp=Dpop(&ds)/dpoptmp; Dpush(&ds,dpoptmp); break; push(&os,D); *exp+; break; case %: if(!IsEmpty(&os) | peek(&os).level =Mo.level) switch(pop(&os).op) case % : dpoptmp=Dpop(&ds); dpoptmp=(float)(int)Dpop(&ds)%(int)dpoptmp); Dpush(&ds,dpoptmp); break; case * : dpoptmp=Dpop(&ds)*Dpop(&ds); Dpush(&d