设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法。

#includestdio.h#includestdlib.h#defineMax_Size20#defineMaxSize10typedefcharSElemType;typedefstructlnode{SElemType*base;SElemType*top;intstacksize;}SqStack;voidInitStack(SqStack&S)//初始化栈{S.base=(SElemType*)malloc(Max_Size*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base;S.stacksize=Max_Size;}SElemTypeGetTop(SqStackS)//取得栈顶元素{SElemTypee;if(S.top==S.base)return-1;e=*(S.top-1);returne;}voidPush(SqStack&S,SElemTypee)//元素进栈{if(S.top-S.base=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+MaxSize)*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=MaxSize;}*S.top++=e;}voidPop(SqStack&S,SElemType&e){if(S.top==S.base)exit(-1);e=*--S.top;}intIn(charc)//判断是否为运算符{if((c=='+')||(c=='-')||(c=='*')||(c=='/')||(c=='(')||(c==')')||(c=='#'))return1;elsereturn0;}SElemTypeOperate(SElemTypea,SElemTypem,SElemTypeb)//运算{SElemTypex;switch(m){case'+':x=a+b;break;case'-':x=a-b;break;case'*':x=a*b;break;case'/':x=a/b;break;}returnx;}SElemTypePrecede(SElemTypem,SElemTypen)//判断运算符的优先级{inta[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1},{1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0},{1,1,1,1,2,1,1},{-1,-1,-1,-1,-1,2,0}};switch(m){case'+':m=0;break;case'-':m=1;break;case'*':m=2;break;case'/':m=3;break;case'(':m=4;break;case')':m=5;break;case'#':m=6;break;}switch(n){case'+':n=0;break;case'-':n=1;break;case'*':n=2;break;case'/':n=3;break;case'(':n=4;break;case')':n=5;break;case'#':n=6;break;}returna[m][n];}voidEvaluateExpression()//将中缀表达式转化为后缀表达式并求其值{SqStackOPTR,OPND;SElemTypex,c,a,theta,b;InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();putchar(c);while(c!='#'||(GetTop(OPTR)!='#')){if(!In(c))//不是运算符则进栈{Push(OPND,c);c=getchar();putchar(c);}elseswitch(Precede(GetTop(OPTR),c))//比较栈顶运算符跟当前运算符的优先级{case-1:{Push(OPTR,c);c=getchar();putchar(c);break;}//当前运算符的优先级高，进栈case0:{Pop(OPTR,x);putchar(c);c=getchar();break;}//运算符优先级相同，退栈case1:{Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);putchar(b);putchar(a);putchar(theta);x=Operate(a,theta,b);putchar(x);Push(OPND,x);//将运算结果入栈break;}//当前运算符的优先级低，出栈，参与运算}}printf(\n求值结果：);putchar(GetTop(OPND));printf(\n);}voidmain(){printf(请按顺序输入表达式(表达式以'#'结束，如2*(3+2)#)：\n);EvaluateExpression();}