3.2栈的应用举例3.2.5-表达式求值.ppt

3.2 栈的应用举例3.2.5 表达式求值 算符优先法: 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 进OPND栈 操作符(operator): 进OPTR栈 界限符(delimiter): * 算符间的优先关系: θ1 θ2 + - * / ( ) # + - * / ( ≒ ) # = Precede: 判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间 的优先关系的函数. Operate: 进行二元运算aθb的函数. * 算术表达式求值过程(算法3.4)OperandType EvaluateExpression() {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; default: printf(“Expression error!”); return(ERROR); } // switch } // while return GetTop(OPND); } // EvaluateExpression * 对算术表达式3*(7-2)求值. 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,’3’) 2 # 3 * ( 7 - 2 ) # Push(OPTR,’*’) 3 # * 3 ( 7 - 2 ) # Push(OPTR,’(’) 4 # * ( 3 7 - 2 ) # Push(OPND,’7’) 5 # * ( 3 7 - 2 ) # Push(OPTR,’-’) 6 # * ( - 3 7 2 ) # Push(OPND,’2’) 7 # * ( - 3 7 2 ) # Operate(‘7’,’-‘,’2’) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(‘3’,’*’,’5’) 10 # 15 # Return(GetTop(OPND)) * 例：汉诺塔问题： 将a柱子上的盘移到 c柱，用 b柱放临时盘 要求：一次只能移动一