文档介绍：栈的应用举例 表达式求值 b算符优先法: b 4+2 * 3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 b操作数( operand): 进 OPND 栈 b操作符( operator): 进 OPTR 栈 b界限符( delimiter): 算符间的优先关系: bθ 1 θ 2+-*/()# b + >><<<>> b - > ><<<>> b*>>>><>> b />>>><>> b (<<<<<≒ b )>>>>>> b # < <<<<= Precede: 判定运算符栈的栈顶运算符θ 1与读入的运算符θ 2之间的优先关系的函数. Operate: 进行二元运算 (算法 ) OperandType EvaluateExpression () b{ InitStack (OPTR); Push(OPTR, ‘#’); b InitStack (OPND); c = getchar (); b While (c!= ’#’|| GetTop (OPTR)!= ’#’){ b If( !In(c,OP)){ Push(OPND,c); c = getchar () ;} // 不是运算符则进栈 b else b switch (Precede( GetTop (OPTR),c)){ b case ‘<’: // 栈顶元素优先权低 b Push(OPTR,c); c = getchar () ; break ; b case ‘≒’: // 脱括号并接受下一个字符 b Pop(OPTR,x); c = getchar () ; break ; b case ‘>’: // 退栈并将运算结果入栈 b Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); b Push(OPND,Operate(a,theta,b)); break ; b default: printf (“ Expression error! ”); return(ERROR); b } // switch b } // while b return GetTop (OPND); b } // EvaluateExpression 对算术表达式 3* (7-2) 求值. b步骤 OPTR 栈 OPND 栈输入字符主要操作 b1 # 3 * ( 7 - 2 ) # Push(OPND, ’3’) b2 # 3 * ( 7 - 2 ) # Push(OPTR, ’*’) b3 # * 3 ( 7 - 2 ) # Push(OPTR, ’(’) b4 # * ( 3 7 - 2 ) # Push(OPND, ’7’) b5 # * ( 3 7 - 2 ) # Push(OPTR, ’-’) b6 # * ( - 3 7 2 ) # Push(OPND, ’2’) b7 # * ( - 3 7 2 ) # Operate( ‘7’,’-‘,’2’) b8 # * ( 3 5 ) # POP(OPTR) b9 # * 3 5 # Operate( ‘3’,’*’,’5’) b10 # 15 # Return( GetTop (OPND)) 例:汉诺塔问题: 将a柱子上的盘移到 c柱,用 b柱放临时盘要求:一次只能移动一个盘,大盘不可放于小盘上。 abc hanoi hanoi 塔问题塔问题 b定义函数: movetower (n,a,c,b) n 个盘 a->c,b放临时盘 b分三步: bmovetower (n-1,a,b,c) 将n