2014年考研数据结构辅导(12)
中缀表达式直接求值算法: OPNDType EvalueExpression() { //OPTR 和OPND分别为运算符栈和操作数栈 InitStack(OPTR);Push(OPTR,’#’); InitStack(OPND);c=getchar(); While(c!=’#’|| GetTop(OPTR)!=’#’) { If(!IN(c,OP) ) //如果是操作数,直接入操作数栈 { push(OPND,c); c=getchar(); } Else //如果是运算符,则与当前的栈顶比较 { Switch(Precede(GetTop(OPTR),c)) { Case ‘<’: push(OPTR,c);//比当前栈顶高,这入栈 c=getchar(); break; Case ’= ’:Pop(OPTR,x); //在我们设计的优先级表中, c=getchar(); //只有’(’和’)’存在相等的情况, break; //而在规约中间只存在‘(’‘)’ //所以我们直接把’(’弹出就可以了 Case ‘>’: //比当前栈顶低,则要把栈顶先运算完(先规约) pop(OPTR,theta); //把栈顶运算符弹出 Pop(OPND,b); //取出操作数,并且是前操作数 Pop(OPND,a); //在下面(栈的先进后出) Push(OPND,Operate(a,theta,b)); //运算的结果入栈 //(他是其他运算符的操作数) Break; }//Switch }//else }//whild Return GetTop(OPND);//操作数栈中最后剩下的就是整个表达式的结果了。 } |