数据结构-算术表达式求值算法

.PAGE.XX航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：算术表达式求值算法院〔系：计算机学院专业：计算机科学与技术班级：学号：__指导丁国辉完成日期：20XX01月11日..目录TOC\o"1-3"\h\z第1章概要设计11.1题目的内容与要求11.2总体结构1第2章详细设计32.1栈的顺序存储模块32.2进栈模块32.3出栈模块42.4运算模块42.5判断优先级模块52.6处理表达式主体模块6第3章调试分析8第4章运行结果9参考文献11附录〔程序清单12..第1章概要设计1.1题目的内容与要求内容：设计程序,其能够求解任意给定算数表达式的值,算数表达式中的操作符来自于集合{+,－,*,＼},表达式允许包括小括号"〔",表达式的输入以"#"作为结束标志。要求：利用栈结构实现表达式求值算法,即在约定的条件下,正确输入表达式,经过程序的运行之后,给出表达式的值；系统利用C语言实现；独立完成系统的设计、编码和调试。1.2总体结构本程序主要分为六个模块〔主要算法模块图见图1.1：栈的顺序存储模块、进栈模块、出栈模块、运算模块、判断优先级模块、处理表达式主体模块。栈的顺序存储模块：分别建立两个栈,第一个用来存储运算符,第二个是用来存储数字。进栈模块：运算符和数字分别存储在运算符栈和数字栈中,以便运算时的调用。出栈模块：由于运算的需要,就必须把运算符和数字分别从运算符栈和数字栈中取出来。运算模块：程序在遇到运算符的时候,根据此模块的要求进行运算。判断优先级模块：找出栈顶算符和即将入栈算符的对应的下标,然后根据算符间的优先关系表判断出算符的优先关系。处理表达式主体模块：结合运算模块和判断优先级模块,对表达式进行系统处理,求出算数表达式的值。算术表达式求值算法算术表达式求值算法出栈模块判断优先级模块处理表达式主体模块栈的顺序存储模块运算模块进栈模块图1.1主要算法模块图..第2章详细设计在本次课程设计中,我们用到了栈这个重要的数据结构。在实现程序的功能的时候,有很多重要的程序段是涉及栈方面的：有栈的结构建立,入栈,出栈。另外还有就是对表达式进行运算,判断运算符的优先级,对表达式的主体进行处理。重要的程序段如下。2.1栈的顺序存储模块本课程设计是通过栈为载体来实现程序的功能的,因此栈结构的建立是必不可少的。分别建立两个栈,第一个用来存储运算符,第二个用来存储数字。2.2进栈模块主要是把运算符和数字分别存储在运算符栈和数字栈里面。首先判断栈是否满,若不满就进栈,把e插入为新的栈顶元素；否则就追加存储空间。流程图如图2.1所示。FFT开始判断栈是否满追加存储空间e进栈为新的栈顶元素结束图2.1进栈模块流程图2.3出栈模块主要是把运算符和数字分别从运算符栈和数字栈中取出来。由于运算的需要,此时就必须把运算符和数字从栈中取出来,即出栈。运算符和数字的出栈,是先取出栈顶元素an。由于取出元素之后,原先的栈顶元素的位置为空了。此时an-1就成了栈顶元素了,所以原先的栈顶指针就减一,指向现在的栈顶元素an-1。第一个函数是运算符的出栈,第二个函数是数字的出栈。首先判断栈是否为空,若栈不空,则删除S的栈顶元素,用e返回其值；否则返回ERROR。流程图如图2.2所示。FFT开始判断栈是否空返回ERROR栈顶元素出栈结束图2.2出栈模块流程图2.4运算模块当程序在遇到运算符的时候,就要进行运算。函数中a和b就是代表数字,而theta就是代表运算符。当出栈时栈顶元素是"+"〔加,程序就执行加法运算,最后的结果是a和b两数之和；当出栈时栈顶元素是"-"〔减,程序就执行减法运算,最后的结果是a和b两数之差；当出栈时栈顶元素是"*"〔乘,程序就执行乘法运算,最后的结果是a和b两数之积；当出栈时栈顶元素是"/"〔除,程序就执行除法运算,最后的结果是a和b两数之商。函数的返回值就是函数最后的结果。流程图如图2.3所示。defaultdefault/*-+case开始theta〔运算符a+ba-ba*ba/b错误结束图2.3运算模块流程图2.5判断优先级模块由于我们输入的是四则运算,因此就不得不考虑算符的优先级问题。先调用函数ReturnOpOrd<>找出栈顶算符和即将入栈算符的对应的下标,然后再调用precede<>函数,根据算符间的优先关系表〔如表2.4所示判断出算符的优先关系：a1<a2a1的优先权低于a2；a1=a2a1的优先权等于a2；a1>a2a1的优先权高于a2。上述函数就是判断优先级的函数。经过运算之后,函数返回值即为优先权高低。a2a2a1a1＋－*／〔#＋>><<<>>－>><<<>>*>>>><>>／>>>><>>〔<<<<<=>>>>>>#<<<<<=表2.4算符间的优先关系表2.6处理表达式主体模块此函数就是处理表达式的函数。函数首先判断即将入栈的元素是数字还是符号,若是数字就进OPND栈〔存储数字的栈。若是算符,就调用ReturnOpOrd<>和precede<>函数判断OPTR栈〔存储算符的栈的栈顶元素和即将入栈的元素的优先级。如果栈顶元素的优先权低的话,则这个即将入栈的元素就入栈；如果优先权相同,则脱括号并接收下一字符；如果栈顶元素的优先权高的话,则运算符栈顶元素出栈,且数字栈的栈顶元素出栈,然后调用函数Operate<>进行运算并将运算结果入栈。直到运算完整个表达式为止,函数返回值即为表达式的值。流程图如图2.5所示。FFTcaseF>=<T开始输入表达式*c!='#'||<GetTop<OPTR,e>,e>!='#'不是算符数字进OPND栈〔存储数字的栈运算符进OPTR栈〔存储算符的栈调用ReturnOpOrd<>和precede<>函数判断优先关系Pop<OPTR,x>;c++;〔出栈Pop<OPTR,theta>;Pop<OPND,b>;Pop<OPND,a>;Push<OPND,Operate<a,theta,b>>;return<GetTop<OPND,d>,d>;结束图2.5处理表达式主体模块流程图..第3章调试分析〔1问题：由于输入时的疏忽遗漏了"；"、"}"、""等,编译时出现错误。解决方法：通过编译器的错误提示进行修改,添加一些遗漏的信息。〔2问题：在运行时提示库函数名为未标识符。解决方法：通过编译器的错误提示进行修改,缺少头文件,添加所需的头文件。〔3问题：输出的数只能在97以内,而且只能输入输出整数,不能实现输入输出小数,当输入小数时出现错误解决方法：规范输入输出格式。〔4问题：操作数和运算符在一起发生冲突,当混合输入数据和运算符,出现异常,没有结果。解决方法：使用两个工作栈,一个存储数字,一个存储运算符。..第4章运行结果运行操作及结果：〔1显示输入表达式,以'#'号结束。〔2正确输入表达式,以'#'号结束,就能得到表达式的值。..参考文献[1]严蔚敏,吴伟明.数据结构〔C语言版[M].北京:清华大学出版社,2007[2]王敬华,林萍,张清国.C语言程序设计教程[M]〔第二版.北京:清华大学出版社,2009.8[3]吴海燕,任午令,章志勇.数据结构[M].XX:XX大学出版社,2011.6[4]胡圣荣,周霭如,罗穗萍.数据结构教程与题解[M].北京:清华大学出版社,2011.9[5]谭浩强.C程序设计试题汇编[M].北京:清华大学出版社,2006.3[6]李兵,崔虹燕,马晓亭.C语言程序设计[M].北京:科学出版社,2011..附录〔程序清单#include<stdio.h>#include<string.h>#include<stdlib.h>intInitStack<StackChar&S>intPush<StackChar&S,chare>intPop<StackChar&S,char&e>intGetTop<StackCharS,char&e>unsignedcharstr[7][7]={ '>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=','', '>','>','>','>','','>','>', '<','<','<','<','<','','='}; charOPSET[7]={'+','-','*','/','<','>','#'};floatEvaluateExpression<char*k>{ StackCharOPTR; StackFloatOPND; charT[20]; floatData,a,b; chartheta,*c,x,str[2]; chare; floatd; InitStack<OPTR>; Push<OPTR,'#'>; InitStack<OPND>; c=k; strcpy<T,"\0">; while<*c!='#'||<GetTop<OPTR,e>,e>!='#'> { if<!In<*c,OPSET>> { str[0]=*c; str[1]='\0'; strcat<T,str>; c++; if<In<*c,OPSET>> { Data=<float>atof<T>; Push<OPND,Data>; strcpy<T,"\0">; } } else { switch<precede<<GetTop<OPTR,e>,e>,*c>> { case'<': Push<OPTR,*c>; c++; break; case'=': Pop<OPTR,x>; c++; break; case'>': Pop<OPTR,theta>; Pop<OPND,b>; Pop<OPND,a>; Push<OPND,Operate<a,theta,b>>; break; } } } return<GetTop<OPND,d>,d>;}floatOperate<floata,unsignedchartheta,floatb>{ switch<theta> { case'+': returna+b; case'-': returna-b; case'*': returna*b; case'/': returna/b; default: return0; }} intIn<charTest,char*TestOp>intReturnOpOrd<charop,char*TestOp>{ inti; for<i=0;i<7;i++> { if<op==TestOp[i]>returni; } return0;}charprecede<charA,charB>{ returnstr[ReturnOpOrd<A,OPSET>][ReturnOpOrd<B,OPSET>];}voidmain<>{ chark[100]; floatresult; printf<"输入表达式,以'#'号结束:\n">; gets<k>; result=EvaluateEx