数据结构算术表达式求值课程设计.docx

1 .前言22 .问题描述33 .总体设计错误!未定义书签。3.1 概要设计错误!未定义书签。3.1.1 数据结构的选择33.1.2 相关功能函数33.1.3 函数模块调用关系432详细设计和编码54 .运行与测试94.1 上机调试94.2 算法时间和空间性能分析104.3 程序运行测试结果115 .总结与心得135.1 设计中难点的总结以及其它解决方案135.2 实验心得146 .用户使用说明167 .参考文献168 .附录1（源代码清单）16.附录2（成绩评定表）251.前言课程设计是实践性教学中的一个重要环节，它以某一课程为根底，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业根底课，是计算机理论和应用的核心根底课程。在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程根本内容的理解。同时，在程序设计方法以及上机操作等根本技能和科学作风方面受到比拟系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以到达要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。在这次的课程设计中我选择的题目是表达式的求值演示。它的根本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四那么混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的根本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比拟困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助我完成我的程序设计。2 .问题描述（问题分析和任务定义）在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因此，要求设计一个程序，利用栈演示运算符优先法对算术表达式求值的过程，利用算符有限关系，实现对算数混合四那么运算表达式的求值。程序输入：一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“+”、“/"、“（"、'，），用，铲，表示结束。程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程。测试数据：1024/（4*8）、（20+2）*（62）（用于正确性检测的合法输入数据）9/0（用于健壮性检测的非法输入数据）3 .总体设计3.1 概要设计3.1.1 数据结构的选择任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来存放表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR,用以存放运算符；另一个称做OPND,用以存放操作数或运算结果。首先置操作数栈为空栈，表达式起始符“井”作为运算符栈的栈底元素，然后依次读入表达式的每个字符，假设是操作数那么进入OPND栈，假设是运算符，那么和OpTR栈的栈顶运算符比拟优先权后做相应操作，直至整个表达式求值完毕。栈的抽象数据类型定义ADTSqStack数据对象：D=aiaiElemSet,i=1,2,3,n,nO数据关系：Rl=<ai-l,ai>ai-l,aiDj=1,2,3,，11约定其中ai端为栈底，an端为栈顶。操作集合：见如下相关功能函数ADTSqStack3.1.2 相关功能函数运算符栈的功能函数OpTR栈voidOptr_InitStack(Optr_Stack&S1)运算符栈的初始化voidOptr_Push(Optr_Stack&Sl,chare)运算符栈的栈顶插入新的数据元素charOptr_Pop(Optr_Stack&S1)运算符的栈顶元素出栈charOplr_GetTop(Optr_Stack&S1)取出运算符栈的栈顶元素voidOptr_DispStack(Optr_Stack&S1)从栈底到栈顶依次输出各运算符运算数栈的功能函数OPND栈voidOpnd_InitStack(Opnd_Stack&S2)运算数栈的初始化intGetTop2(SqStack2&S2)获取运算数栈的栈顶元素voidOplr_Push(Optr_Stack&S1,chare)运算数栈的栈顶插入新的数据元素floatOpnd_Pop(Opnd_Stack&S2)运算数栈的栈顶元素出栈voidOpnd_DispStack(Opnd_Stack&S2)从栈底到栈顶依次输出各运算数算术表达式的相关功能函数charPrecede(charm,charn)运算符的优先级比拟函数floatCalculate(floata,charrheta,floatb)运算函数voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)判断算术表达式各字符如何入栈函数3.1.3函数模块调用关系主程序模块:式王：栈的建立及初始化模块判断输入是否结束模块Uf¾t-运算数进栈模块运算符优先级比较模块*王Vf,运算符进栈模块运算符运算数出栈模块,0、运算模块3.2详细设计和编码首先本程序定义两个顺序栈：运算符栈（OPTR）和运算数栈（OPND）；OPTR栈定义如下：typedefstructchar*base;char*top;intstacksize;Optr_Stack;OPND栈定义如下：typedefstructfloat*base;算符栈的栈底算符栈的栈顶算符栈的最大长度操作数栈的栈底float*top;操作数栈的栈顶intstacksize;操作数栈的最大长度Opnd_Stack;然后是主要功能函数的详细设计：(1) charPrecede(charm,charn)判断运算符优先权，返回优先权高的算符间的优先关系如下：'>r-4U+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<函数实现如下：charPrecede(charm,charn)运算符的优先级比拟(if(n=中n=<)输入符号为if(m=*m=*)returnV;栈顶元素为此时栈顶符号优先级低，返回Velsereturn否那么，栈顶符号优先级高,返回)elseif(n='*'n=7')输入的符号为”*”、“/"(if(m=,),m='*,m=,)retum栈顶元素为此时栈顶符号优先级高,返回，elsereturnY;否那么，栈顶符号优先级低,返回)elseif(n=*)returnY;输入的符号为“那么直接返回elseif(n=h)/输入的符号为(if(m=+C)retum1;栈顶元素为“(",此时优先级同，返回“二”elsereturn否那么，栈顶符号优先级高,返回)else输入符号为其他(if(m=罪)return-;栈顶元素为此时优先级同，返回“二”elsereturn少;否那么，栈顶符号优先级高,返回(2) VOidEVaIUate(OPtjStaCk&SIQpncLStack&S2)以字符串形式输入算数表达式,根据是运算符还是运算薪来判断如何入庙函数实现如下：voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)charc;floatt,e;intn=0,i=l,j=O,k=O,l=O;charchSTACKJNIT_SIZE;ints=1;intflag=0,flag2=0;floatpl,p2;charchi;OPtr_Push(SlW);将考入栈,作为低级运算符CoUt<<”请输入不含变量的表达式(以#结束!)：ncin>>ch;c=ch0;cout<<"n病表达式求值的操作过程如下："*n"vv”步骤t运算符栈Slt运算数栈S2t字符表达式tt栈操作过程”；While(CPtJGetToP(S1)!=1#')cout<<i+<<"t;Optr_DispStack(Sl);cout«"ttn;Opnd_DispStack(S2);cout<<'<tt;if(flag=l)flag=O;)if(flag2)k÷=flag2;flag2=0;)for(l=0;l<k;l+)cout<<,;for(j=k;chj!=,0,;j+)cout<<chfj;if(chk!='#'&&flag!=1)k+;flag=O;if(!(c="+c=-'c=,*,c=7,c='('c=,),c=')输入的字符如果不是运算符号，那么继续输入直到输入的是运算符为止，将非运算符转换成浮点数if(!(c=?)&&n>=0)小数点前面的数e=float(c-48);n+;if(n=l)t=e;elseif(n>l)t=t*10+e;转换小数点前面的局部c=chs+;)if(n=-1)小数点后面的数e=float(c-48);转换小数点后面的局部t=t+e1O;c=chs+;最终将转换后的两局部加起来，转换成浮点数)if(c='.')(n=-l;c=chs+;)if(c>=,0,<fc<fec<='9,)c='J)flag2+;gotoas;)if(c<,0'c>,9,)(Opnd_Push(S2,t)；)cout<<"ttOpnd.Push(S2<<t<<n)")else输入的是运算符n=0；非运算型数据计数器清零SWitCh(PreCede(OPtLGetTOP(Sl),c)比拟运算符的优先级(CaSey:栈顶元素优先级低，那么入栈且继续输入Optr_Push(Sl,c);cout«MttOptr_Push(S1,"<<c<<)"c=chs+;breakcase=:/履顶元素优先级相等，脱括号并接收下一字符Optr_Pop(Sl);cout«HttOptr_Pop(S1)h;c=chs+;break;casef:/栈顶元素优先级高，那么退栈并将运算结果入栈pl=Opnd_Pop(S2);p2=Opnd_Pop(S2);ch1=Optr_Pop(S1);Opnd_Push(S2,Calculate(p2,chl,pl);cout<<,ttCalculate(<<p2<<','<<chl<<<,<<pl<<,)r;flag=l;break;cout<<nn*cout<<i<<,t'<<<,<<nttn<<Opnd-GetTop(S2)<<'>tt;for(j=0;j<k;j+)cout<<,;cout«',#',«"ttn«,RETURN(GETTOP(S2)H;cout<<nn*if(S2.top-1=S2.base)/显示表达式最终结果cout<<n表达式的结果为："v<Opnd_GetTop(S2)«endl;elsecout<<"n表达式出错!n”;(3) floatCalculate(floata,chartheta,floatb)运算函数，运用else-if语句，不同的运算符那么进行不同的运算；进行除法时，假设分母为0,那么将标志标记成错误。函数实现如下：floatCalculate(floata,chartheta,floatb)运算函数floattmp=0;if(theta=中)tmp=a+b;从运算符栈取出的符号为“+"，那么运算数栈的两元素相加，并返回elseif(theta='-')tmp=a-b;/从运算符栈取出的符号为“-"，那么运算数栈的两元素相减，并返回elseif(theta=EtmP=a*b;从运算符栈取出的符号为那么运算数栈的两元素相乘，并返回elseif(theta=7)从运算符栈取出的符号为“/"，那么运算数栈的两元素相除，并返回if(b=0)cout<<n表达式出错!除数不能为0!n"elsetmp=ab;returntmp;注：其它函数详细设计及编码详见附录14.运行与测试4.1 上机调试(1) .语法问题及解决由于本程序牵扯到四个方面的内容，首先是OPTR栈的相关功能函数的设计；其次是OPND栈的相关功能函数的设计；再次是算术表达式的具体计算涉及到的相关功能函数的设计，最后是主函数的设计；前两个方面均为对顺序栈的根本操作，具有通用性，根本无语法错误；主要是在设计算术表达式的具体计算的函数时，调用相关栈的函数以及其它语句时，出现了语法编辑的错误，还有在设计主函数的时候，由于要考虑到用户的使用方便,也出现了一些编辑语法错误，在反复使用加注释和单步运行两种方法对于具体错误分析、调试后，所有语法错误均得到解决。(2)逻辑问题及解决程序初步完成以后，进行测试发现出现死循环，观察显示结果发现，栈中的数据和运算符一直都没有出栈。既然没有出栈，那么根据以前程序调试的经验，该问题应该出在栈的出栈操作中，于是找到进行出栈操作的函数，经仔细检查发现，原来将return语句写到了top一语句的前面去了，而etum语句有跳出的作用，当它一旦执行，其后的语句都会被忽略而得不到执行。因此将它们调换顺序，正确写法见源程序。再次调试程序，输入一个测试表达式(如1+2*5#),发现结果是10,而且通过将枝中的数据进行显示发现1并未出栈，而操作符栈的“+”未进行运算便出了栈。通过步步跟踪来走程序发现，原来错误出在优先级判断的条件语句里面，在取出栈顶元素与刚读入的运算符进行比拟时，当刚读入的运算符优先级高于栈顶的运算符时，直接将刚读入的运算符入栈，而刚从栈顶取出的一个运算符却抛之不管，当然会出错，因此应将刚取出的先入栈，然后将刚读入的运算符入栈。经过以上的修改，用一些简单的表达式进行测试发现能得出正确结果，但当输入像-7+1#或-(1+2*3)#这样的开头带负号的表达式时，程序计算的结果与实际相差甚远。因此应将开始的“-”作为负号而不是减号，并进行特殊的处理。当输入的计算数据超过9时(如12+56#),计算结果又出错，通过输出栈中的数据进行观察发现栈将12分成了1和2,将56分成了5和6进行分别存储。这显然是错误的。通过检查程序发现输入语句用的是c=getchar(),该输入语句每次只能得到一个字符，12是两个字符1和2,因此会出现上面的情况。于是将输入改为字符串输入并存入一个字符数组中，然后将字符串转换成相应的运算符和数据以参与计算。通过上面的更改，运行程序发现已经能接受大于9的数据以参与运算了；但当输入一些特殊非运算用符和字母时，又出现了意想不到的错误结果，因此程序采用了相应的算法，在使用刚输入的表达式字符串前，进行严格的检测。4.2 算法时间和空间性能分析时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为0(n)。空间上，由于在本程序中，在为算符栈(OPTR)和操作数栈(OPND)涉及到两种情况时申请空间，一方面分别为OPTR栈和OPND栈申请了初始的存储单元，均为STACJnitsize=100个；另一方面，考虑到两个栈在处理具体的算术表达式时，有可能会出现溢出的情况，即栈的初始的存储空间不够用，这时需要为其申请额外的存储空间，每溢出一次，就为其申请存储单元STACKINCREMENT=10个；所以，本程序的算法的空间复杂度一方面取决于算术表达式的长度，另一方面取决于本程序的所有代码所占用的存储空间大小。4.3程序运行测试结果计算表达式1024/(4*8)1024<4*8>tt药枣芭芒娄堡也避住W型如/步骤运算符栈Sl运算数栈S2字符表达式栈主要操作过程1tt1024<4*8>ttOpnd_Push<S2,1024>2tt1024/<4*8>«OptrJPush<Sl,>3#/1024<4*8>ttOptr_Push<Sl,<>XXX*X*WW*XXXXW*XWX*W*XX*M*X*XWXXWX*MMX*-*X*xxxxzyWW*KX>OfXXxx4tt<10244*8>tt0pnd_Pusb<S2,4>5«/<10244*8>ttOpti»_Push<Sl,*>6#/<*10244*MXXXXMXMMXXXX48>ltOpnd_Push<S2,8>7#/<*102448>ttCalculate<4,*,8>8tt<*M,MMaM1MM1MM,M,M,M,MM,M,MMd102432>«CMM,MMMMMMMM,M,M,MM,MMM,M,MMMM,M,MMaMOptrJPop<Sl>9tt102432UCalculate<1024,32>10tt32nRETURN<GETT0P<S2>>表达式的结果为：32三三IW三0:5是F,CUsersAdministratoDesktopDebugwest.e×e'Lr*a回四睛输入不含变量的表达式(以*结束?)：输入用户选择“1”继续计算表达式3*(7-2)式委为导择y 果续选ke 结继的y 的不林an输入用户选择“0”，退出程序米表达式求值:（0或1）f0tocontinue用“9/0”验证在除法中除数不能为0I"C:UsersAdministratorDesktopDebugwest.exe'Bll回请输入不含变量的表达式（以M结束?）：9/0#对表达式求值的操作过程如下：誉L仙点黑黑热nEum三譬警冷门EEn烹阴盛普索EEj书胃理解落Ieeeeue1tt90tt0pnd_Push<S2,9>2tt9/0«Optr_Push<Sl,/>XX-XXXKXXXXXXM*X*XXXXXMWXWXX-XM充XMXXX*WXX*X*WM*WX*W*-*3tt90ttOpndJPush<S2,0>4tt90U表达式出错?除数不能为0?结果分析：以上调试结果是正确的。能够实现各个符号优先级先后顺序的运算，根据符号优先级（、）、+、*、/,如此顺序进行运算，实现了根本表达式运算的功能。a.可以完成四那么混合运算b.可以检查表达式的输入是否正确c.演示表达式的求值的操作过程5.总结与心得5.1设计中难点的总结以及其它解决方案难点一：如何实现“算符优先关系”的比拟本报告方案：利用if-else语句实现运算符优先级的比拟。其它方案：行和列都按照中、7'、（'、）、罪的顺序，将优先关系表存储在一个二维数组P中。判别两个运算符的优先关系就转化为查找相应的二维数组的元素值的过程：charPrecede（charc1,charc2）根据操作符Cl和c2的序号确定其优先关系Pij。it i,j;char P77=X>l<7<'<7>','>'J,>V>V<'<V<V>V>>,$<,>V>,>7>VS7>7>,<,<,<',<V<,S,=,);i=LocateChar(cl);定位Cl在中、中的位序，从0开始计数j=LocateChar(c2);定位c2在7'、中的位序，从0开始计数if(PiL11=二$)coutv<"算符不匹配！t4;break;returnPij;)难点二：如何设定栈中元素的类型本报告方案：设立两套栈的定义和操作，即分别定义数据元素为Char型和数据元素为float型的两个栈，并且设定两种不同类型数据的栈的PUSh、Pop等操作。这样做的好处在于，将数字的运算范围扩大到float,不同类型的元素存储的时候“各得其所”,互不影响，缺点在于程序会写得重复而冗长。其它方案：只定义一种栈的类型，即把栈中的元素统一定义为float型，只需在实现CaICUIate函数的时候，对“theta”进行强制类型转换即可，虽然外表上会造成精度缺失，但theta本身是一个字符，也算是整型，故对于运算结果不会有影响。SElemTypeCalculate(SElemTypea,SElemTypetheta,SElemTypeb)/Calculate为进行二元运算的athetab的函数charn=char(theta);此处把double型强制转换成Char型switch(n)转换后相当于和符号匹配ACSH码case'+':returna+b;case,-,:returna-b;case,*,:returna*b;case,:returna/b;)难点三：如何将连续的数字字符及小数点转换为实型数字本报告方案：分别转换小数点之前的局部和小数点之后的局部，再把两局部求和。其它方案：定义一个字符数组Datai,用来存储数字字符及小数点构成的子串，利用函数atof,可以很容易地将其转换为相应的实型数字：floatChartoFloat2()inti=0;charc;floatd;c=getchar();while(c>=，0,&&c<=，9,|c=，.,)(Datai=c;i+；c=getchar();)Datai='0'数字没有存满,输入字符串结束符d=atof(Data);此处是把数组里的数字(实际上是按字符串)转换为double类型returnd;)5.2实验心得通过此次课程设计，使我更加扎实的掌握了有关数据结构栈方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在,也暴露出了前期我在这方面的知识欠缺和经验缺乏。实践出真知，通过亲自动手制作，使我掌握的知识不再是纸上谈兵，而且通过实际操作，我也发现我的好多缺乏之处：(1)用栈的结构来解决表达式的求值，首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。开始有些茫然，后来通过结合课本和同学的帮助完成了该课题。(2)对一些看似简单的东西掌握不够熟练，比方由于函数的调用参数问题不熟而造成了调试的困难。对于语法的掌握也欠缺成熟，需要进一步掌握。(3)栈的结构理解不够清晰，造成了设计程序时理不清头绪，需要对数据结构有更深层次的理解。这不仅要求要端正自己学习的态度，更要求要对程序设计报以严谨的态度，我希望自己在以后的学习能更多的用到这些知识。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟,不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫大焉”的知行观。在今后社会的开展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可！课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，但它同时又是一门讲道课，一门辩思课，给了我许多道，给了我很多思，给了我莫大的空间。同时，设计让我感触很深，使我对抽象的理论有了具体的认识，在这个过程中，我不仅培养了独立思考、动手操作的能力，还在各种其它能力上也都有了提高。更重要的是，在实践中，我学会了很多学习的方法，而这是日后最实用的，也是最受益匪浅的。要面对社会的挑战,只有不断的学习、实践，再学习、再实践，这对于我们的将来也有很大的帮助。此外，本次课程设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教老师或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识，收获肯定也会颇丰！6 .用户使用说明：(1)使用环境：VisualC+6.0.(2)操作要求：程序运行后,用户根据提示输入合法的不含变量的算术表达式，以“#”输入结束，即可以计算出结果，并看到运算符与运算数栈的操作过程，之后用户再根据提示，选择是否还要继续进行算术表达式的运算，是那么继续输入，否那么退出程序。7 .参考文献1严蔚敏，吴伟民.数据结构(C语言版)M.北京：清华大学版社，20072严蔚敏，吴伟民,米宁.数据结构习题集(C语言版)M.北京：清华大学版社,20073王淑礼，王新霞.算术表达式求值算法实现的难点剖析J.福建电脑，2012年第3期：4唐蔼明，谢泉钦.算术表达式程序设计算法分析J.闽江学院学报，24(2),2013年4月5殷人昆.数据结构(C+版)M.北京：清华大学版社，20018 .附录(源程序清单)ttinclude<iostream>usingnamespacestd;defineSTACK_INIT_SIZE100defineSTACKINCREMENT10typedefstruct运算符栈(char*base;char*top;intstacksize;0ptrStack;typedefstruct运算数栈(float*base;float*top;intstacksize;OpndStack;voidOptrInitStack(0ptrStack&S1);声明栈建立运算符函数voidOpndInitStack(0pndStack&S2);声明栈建立运算数数函数voidEvaluate(0ptrStack&S1,OpndStack&S2);声明确定如何入栈函数voidOptrPush(0ptrStack&S1,chare);/声明运算符入栈函数voidOpnd_Push(Opnd_Stack&S2,floate);声明运算数入栈函数charOptr_GetTop(Optr_Stack&S1)；声明取运算符栈顶元素函数floatOpnd_GetTop(Opnd_Stack&S2);声明取运算数栈顶元素函数charOptr_Pop(Optr_Stack&S1);声明运算符出栈函数floatOpnd_Pop(Opnd_Stack&S2);声明运算数出栈函数charPrecede(charm,charn);声明运算符优先级比拟函数floatCalculate(floata,charrheta,floatb);/声明运算表达式函数voidOptr_DispStack(Optr_Stack&S1)；从运算符栈底到栈顶依次输出各运算符voidOpnd_DispStack(Opnd_Stack&S2);从运算数栈底到栈顶依次输出各运算数intmain()(Optr_StackS1;定义运算符栈Opnd_StackS2;定义运算数栈/freopen(zzdatal.in,r”,stdin);/freopen(zzdatal.out","w，stdout);intfIag=I;While(flag)可以反复进行算术表达式的求值intm;Optr-InitStack(Sl);调用运算符栈建立函数Opnd-InitStack(S2);调用运算数栈建立函数Evaluate(SI,S2);输入字符表达式确定如何入栈函数CoUt<<请问是否继续算术表达式求值：0:否1:是<<endl;与用户进行简单的会话是否继续，输入1就继续，0就退出COUt<<请输入你的选择(0或1)：；cin>>m;flag=m;)return0;/*运算符栈函数*/void0ptr_InitStack(0ptr_Stack&S1)构造一个空运算符栈Sl(SI.base=(char*)malIoc(STACK_INIT_SIZE*sizeof(char);if(!S1.base)cout<<"存储分配失败！;存储分配失败SI.top=Sl.base;SI.StaCkSiZe=STACK_INnLSIZE;)voidOptr_Push(Optr_Stack&S1,chare)运算符入栈(if(SI.top-Sl.base>=Sl.StaCkSiZe)如果栈满，追加存储空间(SI.base=(char*)realIoc(SI.base,(SI.stacksize+STACKINCREMENT)*sizeof(char)if(!S1.base)COUt<<"存储分配失败！；else(51. top=Sl.base+Sl.stacksize;52. Stacksize=Sl.stacksize+STACKINCREMENT;)*S1.top=e;Sl.top=Sl.top+1;将运算符压入栈中，指针上移)charOptr_GetTop(Optr_Stack&S1)取栈顶运算符(chare;if(SI.top=Sl.base)COUt<<"nttt运算符栈已空！n”;elsee=*(SI.top-1);returne;)voidOptr_DispStack(Optr_Stack&S1)从运算符栈底到栈顶依次输出各运算符(chare,*p;if(SI.top=Sl.base)cout<<zz；else(p=Sl.base;while(p<Sl.top)(e=*p;P+;cout<<e;)charOptr_Pop(Optr_Stack&S1)运算符出栈chare;if(SI.top=Sl.base)COUt<<"nttt运算符栈已空！n”;e=*(一SI.top);returne;)/*运算数栈函数*/voidOpnd_InitStack(Opnd_Stack&S2)构造一个空运算数栈S2(52. base=(float*)malloc(STACK_INIT_SIZE*sizeof(float);if(!S2.base)cout<<"存储分配失败！;存储分配失败52. top=S2.base;52. stacksize=STACK_INIT_SIZE;)voidOPnd_Push(OPnd_Stack&S2,floate)运算数入栈(if(S2.top-S2.base>=S2.StaCkSiZe)栈满，追加存储空间(52. base=(float*)realIoc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float)；if(!S2.base)cout<<“存储分配失败!”;else(52. top=S2.base+S2.stacksize;53. stacksize=S2.stacksize+STACKINCREMENT;)*S2.top=e;S2.top=S2.top+1;将数C入栈，指针上移)voidOpnd_DispStack(Opnd_Stack&S2)从运算数栈底到栈顶依次输出各元素(floate,*p;if(S2.top=S2.base)cout<<zz；else(p=S2.base;while(p<S2.top)e=*p;P+;cout<<e;)floatOpnd_GetTop(Opnd_Stack&S2)取栈顶元素floate;if(S2.top=S2.base)COUt<<"ntt运算数栈已空！”;elsee=*(S2.top-1);returne;)floatOpnd_Pop(Opnd_Stack&S2)出栈floate;if(S2.top=S2.base)cout<<"ntt运算数栈已空！”;e=*(一S2.top);returne;)/*输入表达式确定如何入栈函数*/voidEvaluate(Optr_Stack&S1,Opnd_Stack&S2)charc;floatt,e;intn=0,i=l,j=0,k=0,1=0;charchSTACK_INIT_SIZE;i