32栈的应用举例 325表达式求值 算符优先法: 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 操作数( operand):进OPND栈 操作符( operator):进OPTR栈 界限符( delimiter):
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):
算符间的优先关系: 0 -2/()# <<< Precede:判定运算符栈的栈顶运算符01与读入的运算符02之间 的优先关系的函数 Operate:进行二元运算a0b的函数
算符间的优先关系: θ1 θ2 + - * / ( ) # + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < ≒ ) > > > > > > # < < < < < = Precede: 判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间 的优先关系的函数. Operate: 进行二元运算aθb的函数
算术表达式求值过程算法3.4) OperandType Evaluate Expression( fInitStack(OPTR), Push(OPTR, # InitStack(OPND); c= getchar While(c!=#' Get Top(OPTR)!=#) If(!n(c,OP){Push(OPND,c);c= getchar;}∥不是运算符则进栈 else switch(Precede( Get Top(OPTR), c)i 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) 1//switch 3// while return GetTop(OPND) }∥ Evaluate Expression
算术表达式求值过程(算法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栈|输入字符 主要操作 3*(7-2)#Push(OPND,3”) *(7-2)# Push(OPTR, * 123456789 ##### (7-2)# Push(OPTR,,() ***** 333 7-2)# Push(OPND, 7) 37 2 )# Push(OPTR,"-) 37 2)# Push(OPND, 2) 372 )# Operate(7”,…,2”) ) POP(OPTR) Operate(3,,7*7,75) 10 # 15 Return( Get Top(OPND)
对算术表达式 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))
血an0塔间题 例:汉诺塔问题: 将a柱子上的盘移到c柱,用b柱放临时盘 要求:一次只能移动一个盘,大盘不可放于小盘上。 b
例：汉诺塔问题： 将a柱子上的盘移到 c柱，用 b柱放临时盘 要求：一次只能移动一个盘，大盘不可放于小盘上。 a b c hanoi塔问题