搜索
数据结构课程设计报告栈的应用：表达式求值的设计专业学生姓名班级学号指导教师徐燕萍完成日期目录1设计内容…………………………………………………….12设计分析2.1系统需求分析……………………………………………..12.1.1系统目标………………………………………………...12.1.2主体功能………………………………………………...12.2系统概要设计……………………………………………..12.2.1系统的功能模块划分………….………………………..12.2.2系统流程图…………………………………...…………23设计实践3.1基本分析…………………………………………………..33.2中缀表达式求值…………………………………………..43.3后缀表达式求值…………………………………………..53.4中缀表达式转换成后缀表达式…………………………..64测试方法4.1基本测试…………………………………………………..74.2拓展测试…………………………………………………..74.3容错测试…………………………………………………..85程序运行效果……………………………………………….76设计心得…………………………………………………….87附录：源代码……………………………………………….10栈的应用：表达式求值的设计1设计内容设计一个表达式求值的程序。该程序必须可以接受包含（，），+，-，*，/，%，和^（求幂运算符，a^b=ab）的中缀表达式，并求出结果。如果表达式正确，则输出表达式的结果；如果表达式非法，则输出错误信息。2设计分析2.1系统需求分析2.1.1系统目标利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的中缀表达式转换为后缀表达式，然后读取后缀表达式，输出结果。输入要求：程序从“input.txt”文件中读取信息，在这个文件中如果有多个中缀表达式，则每个表达式独占一行，程序的读取操作在文件的结尾处停止。输出要求：对于每一个表达式，将其结果放在“output.txt”文件的每一行中。这些结果可能是值（精确到小数点后两位），也可能是错误信息“ERRORININFIXNOTATION”。2.1.2主体功能能够处理以字符序列的形式输入的不含变量的实数表达式，正确处理负数与小数，判断表达式是否语法正确（包含分母不能为零的情况），正确实现对算术四则混合运算表达式的求值，能够将计算中遇到的问题和结果以文件的形式予以存储。2.2系统概要设计2.2.1系统的功能模块划分1.判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回‘1’，不是就返回‘0’。2.求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，在根据数字的大小判断优先级。‘+’，‘-’优先级相同，返回数字相同，‘*’，‘/’也是。3.表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。4.主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋值到浮点型的result，输出result。5.两个栈的函数设计：栈的初始化函数charInit_SeqStack()Init_SeqStack()栈判空Empty_SeqStack()charEmpty_SeqStack()入栈函数Push_SeqStack()charPush_SeqStack()出栈函数Pop_SeqStack()charPop_SeqStack()取栈顶函数GetTop_SeqStack()charGetTop_SeqStack()销毁栈Destory_SeqStack()charDestory_SeqStack()2.2.2系统流程图图1系统流程图3设计实践3.1基本分析在计算机中，算术表达式的计算往往是通过使用栈来实现的。所以，本表达式求值程序的最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数和运算符以及改变运算次序的圆括号连接而成的式子。表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。开始优先级比较算法Operate算法建立栈存放操作字符存放数据计算结束表达式是否合法输出表达是值输出错误提示3.2中缀表达式求值中缀表达式：每个二目运算符在两个运算量的中间，假设操作数是整型常数，运算符只含加、减、乘、除等四种运算符，界限符有左右括号和表达式起始、结束符“＃”，如：＃(7+15)*(23-28/4)＃。要对一个简单的算术表达式求值，首先要了解算术四则运算的规则，即：(1)从左到右；(2)先乘除，后加减；(3)先括号内，后括号外。运算符和界限符可统称为算符，它们构成的集合命名为OPS。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符θ1和θ2之间的优先关系必为下面三种关系之一：θ1θ2，θ1的优先权低于θ2。θ1=θ2，θ1的优先权等于θ2。θ1θ2，θ1的优先权高于θ2。实现算符优先算法时需要使用两个工作栈：一个称作operator，用以存放运算符；另一个称作operand，用以存放操作数或运算的中间结果。算法的基本过程如下：首先初始化操作数栈operand和运算符栈operator，并将表达式起始符“＃”压入运算符栈；依次读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求解结束。intExpEvaluation(){/*读入一个简单算术表达式并计算其值。*/InitStack(&operand);InitStack(&operator);PushStack(&operator,’＃’);printf(″\n\nPleaseinputanexpression(Endingwith＃):″);ch=getchar();/*读入表达式中的一个字符*/while(ch!=‘＃’||GetTop(operator)!=‘＃’){if(!In(ch,OPS))/*判断ch是否运算符*/{a=GetNumber(&ch);/*用ch逐个读入操作数的各位数码，并转化为十进制数a*/PushStack(&operand,a);}elseswitch(Compare(GetTop(operator),ch)){case′′:PushStack(&operator,ch);ch=getchar();break;case′=′:PopStack(&operator,&x);ch=getchar();break;case′′:PopStack(&operator,&op);PopStack(&operand,&b);PopStack(&operand,&a);v=Execute(a,op,b);PushStack(&operand,v);break;}}v=GetTop(operand);return(v);}为了处理方便，编译程序常把中缀表达式首先转换成等价的后缀表达式，后缀表达式的运算符在运算对象之后。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，而不用再考虑运算规则和级别。中缀表达式“（a+b*c）-d/e”的后缀表达式为：“abc*+de/-”。3.3后缀表达式求值计算一个后缀表达式，算法上比计算一个中缀表达式简单的多。这是因为表达式中即无括号又无优先级的约束。具体做法：只使用一个对象栈，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时送入栈顶的值就是结果。下面是后缀表达式求值的算法，在下面的算法中假设，每个表达式是合乎语法的，并且假设后缀表达式已被存入一个足够大的字符数组A中，且以‘#’为结束字符，为了简化问题，限定运算数的位数仅为一位且忽略了数字字符串与相对应的数据之间的转换问题。doublecalcul_exp(char*A)/*本函数返回由后缀表达式A表示的表达式运算结果*/{SeqStarcks;ch=*A++;InitStack(s);while(ch!=’#’){if(ch!=运算符)PushStack(s,ch);else{PopStack(s,&a);PopStack(s,&b);/*取出两个运算量*/switch(ch){casech==’+’：c=a+b;break;casech==’-’：c=a-b;break;casech==’*’：c=a*b;break;casech==’/’：c=a/b;break;casech==’%’：c=a%b;break;}PushStack(s,c);}ch=*A++;}PopStack(s,result);returnresult;}3.4中缀表达式转换成后缀表达式将中缀表达式转化为后缀表达式和前述对中缀表达式求值的方法完全类似，但只需要运算符栈，遇到运算对象时直接放后缀表达式的存储区，假设中缀表达式本身合法且在字符数组A中，转换后的后缀表达式存储在字符数组B中。具体做法：遇到运算对象顺序向存储后缀表达式的B数组中存放，遇到运算符时类似于中缀表达式求值时对运算符的处理过程，但运算符出栈后不是进行相应的运算，而是将其送入B中存放。读者不难写出算法，在此不在赘述。程序的整体算法分两步：第一步，从”input.txt”文件中读取中缀表达式，并应用运算符栈OpHolder把中缀表达式转换为后缀表达式，将输出结果存放在一个temp文件中。第二步，从temp文件中读取中缀表达式，并应用操作栈Operands计算后缀表达式结果，将结果输出到”output.txt”文件中。4测试方法设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。5程序运行效果5.1基本测试：在input文件中输入表达式如下图2：则输出结果如下图3：图2图3图45.2扩展测试：在input文件中输入表达式如下图5：则输出结果如下图6：图5图65.3容错测试：在input文件中输入表达式如下图7：则输出结果如下图8：图7图86设计心得通过此次的课程设计，巩固和加深了我对栈、队列、字符串等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（；提高利用计算机分析解决综合性实际问题的基本能力。在细节问题的分析上，较以往有了很大的提高。在寻求最优解的问题上，也能够找到多种解决方案来使自己的程序收放自如。如，在处理实数的问题上，我采用的是每取得一个字符，就立刻对此字符进行处理的方法。其实，我们可以用一个字符数组，来存储连接着的一系列数字字符，然后再通过atof函数，直接得到字符数组中所存储的数字。再如，对负数问题的处理上，我最初的想法是通过一个标志mark来记录前面的字符是否是负号（或减号），再在后面取到除符号外的数字时，选择是否添加负号。另外，与其他人不同的是，