数据结构-算术表达式求值含需求分析和源代码

1、需求分析（附代码）一、需求分析（1）首先定义两个栈OPTROPND,栈OPTRffl于存放运算符，栈OPND用于存放操作数；定义一个一维数组expr存放表达式串。（2）主函数主要包括两部分：（1）判断运算符优先权，返回优先权高的；（2）操作函数。（3）开始将'#<操作符栈，通过一个函数来判别算术运算符的优先级。且规定韵优先级最低。在输入表达式的最后输入#'代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈。遇到运算符则与栈顶运算符比较优先级，当前运算符优先级高（前面的运算还不应执行）则当前运算符入栈，扫描下一符号；否则栈顶运算符出栈，两操作数出栈，进行运算，所得结

2、果入数栈，重新比较当前运算符（注意当前运算符未变）与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#运算结束。（4）最初实现的加、减、乘、除及带小括号的基本运算，但考虑到实用性，后来的设计中有加上了乘方运算。在乘方运算中借用了C库中自带的乘方函数pow。二、概要设计1、设定栈的抽象数据类型定义：ADTStack数据对象：D=ai|aiEElemSet,i=1,2，,n,n>0数据关系：R1=<ai-1,ai>|ai-1,aiD,i=2,n约定an端为栈顶，a1端为栈底。1/29基本操作:InitStack(&S)操作结果：构造一个空栈SDestroyStack(&

3、amp;S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE否则FALEStackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S)初始条件：栈S已存在且非空。2/29操作结果：删除S的栈顶元素，并用e返回其

4、值。ADTStack2、表达式的抽象数据类型ADTarithmetic(数据对象：D1=+-'、飞'/''#',八D2=ala2a3a4基本操作：intIn(intc)判断输入字符c是否为运算符，返回1,则c为操作符，返回0则c不是操作符charprecede(inttop,charc)/判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回>'前一个运算符小于当前运算符的优先级则返<当前一个运算符为'('当前运算符为)时返回='用于去除表达式的括号。elemtypeoperate

5、(elemtypea,chartheta,elemtypeb)计算运算过程中的两个数的值，a,b为两个操作数，theta为操作符，成功，返回两个数的运算结果elemtypeevaluate(structSqstackopnd,structSqstackoptr)/求表达式的值的整个操作过程，通过调用相应的函数实现遇到运算符则与栈顶运算符比较优先级，当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈，扫描下一符号；否则栈顶运算符出栈，两操作数出栈，进行运算，所得结果入数栈，重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#运算结束。3/29)3

6、、本程序包含的模块:(1)、主程序模块voidmain()(structSqstackopnd;操作数栈structSqstackoptr;/操作符栈elemtyperesult;result=evaluate(opnd,optr);printf("theresultis%d'n",result);)(2)运算模块一一实现数据表达式的运算(3)栈模块一一实现栈抽象数据类型模块调用关系：5、计算表达式的伪码初始化操作符栈将/操作符栈初始化操作数栈输入字符cwhile(c!='#'|gettop(optr)!='#')(4/29如果c是操

7、作数（如果flag=1;将操作数栈的栈顶元素出栈，和c共同转化为相应的int类型的数后入操作数栈若flag=0则将c-48入操作数栈flag=1;输入c）否则将c和操作符栈的栈顶元素比较若c的优先级高于栈顶元素C入操作符栈输入下一个字符c若为c与栈顶元素是一对括号，则将栈顶元素出栈输入下一字符c若c的优先级低于栈顶元素则计算操作数栈的栈顶的两个元素的运算，后将运算结果入栈）/while5/29三、详细设计1、输入字符为char类型栈结构structSqstack(elemtype*top;/栈顶指针elemtype*base;/栈底指针intstacksize;栈的大小)；2、栈的基本操作(1

8、)初始化栈statusinitstack(structSqstack&s)(s.base=(elemtype*)malloc(stack_size*sizeof(elemtype);if(!s.base)returnOVERFLOW;s.top=s.base;s.stacksize=stack_size;returnOK;)(2)入栈statuspush(structSqstack&s,elemtypee)6/29(if(s.top-s.base>=s.stacksize)(s.base=(elemtype*)realloc(s.base,(s.stacksize+sta

9、ck_increasement)*sizeof(elemtype)；if(!(s.base)returnOVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;*s.top+=e;returnOK;(3)出栈elemtypepop(structSqstack&s)(elemtypee;if(s.top=s.base)returnERROR;e=*-s.top;returne;7/29(4)取栈顶元素elemtypegettop(structSqstack&s)(elemtypee;if(s.top=s.

10、base)returnERROR;e=*(s.top-1);returne;3、判断c是否是操作数代码具体设计：intIn(intc)判断输入字符是否为运算符，返回1,则c为操作符，返回0则c不是操作符charp10="+-*/()#A"inti=0;while(pi!='0')if(pi=c)return1;i+;8/29return0;)6、判断运算符的优先级+*八()#+>>>>><><->>9/29>><><*<<>>><&g

11、t;<<<>>><>10/29<A<<<<><><(<<<<<<<)>>>>>=>#>>>>>>算数符优先关系模块一一描述算符之间的优先关系，如下表：charprecede(chartop,charc)/top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回<'的优先级小于top'>'c与top构成括号匹配返回'=

12、9;(charresult;11/29switch(c)(case'#':result='>'break;case'+':case'-':if(top='#'|top='(')result='<'elseresult='>'break;case'*':case'/':if(top='*'|top='/'|top=，A，)result='>'elseresult=&#

13、39;<'break;case')':if(top='(')result='='elseresult='>'break;12/29result='<'break;case'A'-result='<'break;default:printf("theoperaterisoutofband.n");)returnresult;)5、将输入的字符数据转换为相应的int类型(1)若为各位数，则直接将输入的字符减48后入栈，若为多位数，则通过

14、flag来实现。(2)若输入字符c为操作数且flag=1,则将操作数栈的栈顶元素出栈后乘以10,然后加上，(c-48)然后将二者的和入操作数栈。代码设计：if(!In(c)/c若为操作数则入opnd栈if(flag=1)e=pop(opnd);push(opnd,(e*10+(c-48);)else13/29push(opnd,c-48);flag=1；c=getchar();)6、具体运算函数elemtypeoperate(elemtypea,chartheta,elemtypeb)该函数实现相应的加、减、乘、除、乘方及带小括号的基本数学运算elemtyperesult;switch(the

15、ta)case'+':result=a+b;break;case'-':result=a-b;break;case'*':result=a*b;break;case'/':if(b=0)/当除数为0时printf("分母为14/29errorn");result=0;)elseresult=a/b;break;case'A'-result=(int)pow(double)a,(double)b);break;default:printf("theoperateriswrong.n&qu

16、ot;);)returnresult;)7、运算主函数elemtypeevaluate(structSqstackopnd,structSqstackoptr)elemtypea,b,c,theta,e;0,theresultisinitstack(optr);/初始化操作符栈push(optr,'#');initstack(opnd);/初始化操作数栈c=getchar();intflag=0;输入的时操作数时，将flag=1;输入为操作符时flag=0;当前输入为操作数且flag=1时，将操作数栈的栈顶元素出栈，15/29/然后和当前输入转换成相应的int类型while(c

17、!='#'|gettop(optr)!='#')(if(!In(c)/c若为操作数则入opnd栈(if(flag=1)(e=pop(opnd);取栈顶元素push(opnd,(e*10+(c-48);/将取出的栈顶元素，与当前操作数相加，后将结果如操作数栈elsepush(opnd,c-48);将操作数直接入栈flag=1;c=getchar();else(flag=0;/当前字符为操作码，则如操作符栈，并将flag置为0switch(precede(gettop(optr),c)16/29/判断当前操作数与操作符栈中的栈顶元素的优先级case'<

18、':push(optr,c);c=getchar();break;若当前操作符的优先级高于操作符栈的栈顶元素，则将前操作符入操作符栈case'=':e=pop(optr);c=getchar();break;若当前操作符与操作符栈的栈顶元素构成匹配的括号，则将操作符栈顶元素出栈case'>':theta=pop(optr);b=pop(opnd);a=pop(opnd);push(opnd,operate(a,theta,b);break;若当前操作符的优先级低于操作符栈的栈顶元素，则将操作符栈栈顶元素出栈，并将操作数栈的栈顶两个元素出栈，计算17

19、/29/两个元素以操作符栈顶元素的数学运算/switch)/whilereturnpop(opnd);函数调用关系图evaluate()main()主函数nitstackgettoplnpoppushprecedepushgettopoperate四、调试分析1、输入的操作数和操作码由于是字符串类型的，在原设计中实现的操作都是对个位数实现的。由于仅是对个位数的运算，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算。开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中有实现了乘方的运算。2、本设计的关键是运算

20、符优先级的判断，由于优先级的错判，很容导致结果的运算错误。要明晰判断当前运算符和运算符栈栈顶元素的先后顺序，这个易出错误。3、在本次设计中充分利用了，栈先进后出的特点。4、该设计的内存分配：初始化栈时，每个栈分配100个内存单元，如果不够用，以后每次可增加10个动态内存单元。18/295、由于程序比较长，在调试期间，可以再每个调用函数中加上printf语句，通过观察程序的运行过程，理由查找错误，和改进程序。6、程序时间复杂度为O(n);7、该设计，自顶向下，分层设计，将每个功能模块化，简洁明了。8、经验体会：借助DEBUG调试器和数据观察窗口，可以加快找到程序的瑕点9、要注意在算数运算中，除数

21、不能为0,在开始的设计中没有注意到这一点。10、在表达式的运算中，要注意输入的是字符串，应将其转换为相应的整形类型的数据再进行运算。否则将出错。并且应当操作数的出栈顺序，以及相应的运算顺序，先出栈的为第二操作数，第二次出栈的为第一操作数。五、用户手册1、本程序的运行环境为DOS操作系统，执行文件为：LiangHong.exe2进入演示程序后，即显示文本方式的用户界面：*请输入算术表达式，以错尾*3、输入算数表达式后，并以籍尾，按回车键，即可得到运算结果六、测试结果输入结果3*(7-2)#theresultis158#theresultis81+2+3+4#theresultis1088-1*5

22、#theresultis8319/291024/4*8#theresultis20481024/(4*8)#theresultis32(20+2)*(6/2)#theresultis663-3-3#theresultis-38/(9-9)#分母为0,theresultiserror2*(6+2*(3+6*(6+6)#theresultis312(6+6)*6+3)*2+6)*2#theresultis3122八10#theresultis10243八(5-(6+7)+6+7-5)#theresultis1附原代码：#include<stdio.h>#include<mallo

23、c.h>#include<math.h>#definestack_size100# definestack_increasement10# defineOK1# defineTRUE1# defineFALSE0# defineERROR0# defineINFEASIBLE-1# defineOVERFLOW-220/29typedefintstatus;typedefintelemtype;structSqstack(elemtype*top;elemtype*base;intstacksize;statusinitstack(structSqstack&s)(s

24、.base=(elemtype*)malloc(stack_size*sizeof(elemtype);if(!s.base)returnOVERFLOW;s.top=s.base;s.stacksize=stack_size;returnOK;elemtypegettop(structSqstack&s)(elemtypee;if(s.top=s.base)returnERROR;21/29e=*(s.top-1);returne;)statuspush(structSqstack&s,elemtypee)(if(s.top-s.base>=s.stacksize)(s

25、.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype);if(!(s.base)returnOVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;)*s.top+=e;returnOK;)elemtypepop(structSqstack&s)(elemtypee;if(s.top=s.base)22/29returnERROR;e=*-s.top;returne;)intln(intc)判断输入字符是

26、否为运算符，返回1,则c为操作符，返回0则c不是操作符(charp10="+-*/()#A"inti=0;while(pi!='0')(if(Pi=c)return1;i+;)return0;)charprecede(chartop,charc)/top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回'<',c的优先/级小于top'>',c与top构成括号匹配返回'='23/29charresult;switch(c)(case'#':result='>

27、;'break;case'+':case'-':if(top='#'|top='(')result='<'elseresult='>'break;case'*':result='>'elseresult='<'break;case')':elseresult='>'break;case'/':if(top='*'11top='/'11t

28、op='八')if(top='(')result='='24/29case'(':result='<'break;case'A':result='<'break;default:printf("theoperaterisoutofband.n");/switchreturnresult;elemtypeoperate(elemtypea,chartheta,elemtypeb)(elemtyperesult;switch(theta)(case'+':result=a+b;break;case'-':result=a-b;break;case'*':result=a*b;break;case'/':if(b=0)25/29(printf("分母为resultiserrorn");result=0;)elseresult=a/b;break;case'A'-result=(int)pow(double)a,(double)b);break;default:printf("the