文档介绍：栈的应用举例 表达式求值
算符优先法:
4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8
操作数(operand): 进OPND栈
操作符(operator): 进OPTR栈
界限符(delimiter):
1
算符间的优先关系:
θ1 θ2 + - * / ( ) #
+ > > < < < > >
- > > < < < > >
* > > > > < > >
/ > > > > < > >
( < < < < < ≒
) > > > > > >
# < < < < < =
Precede: 判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间
的优先关系的函数.
Operate: 进行二元运算aθb的函数.
2
算术表达式求值过程() 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
对算术表达式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 # Retur