要实现这个表达式的求解,可以用算符优先算法。
定义两个工作栈,一个称作OPTR,用以寄存运算符;另一个称作OPND,用以寄存操作数或运算结果。
算法的基本思想是:
1. 首先置操作数为空栈,表达式起始符“#”为运算符栈的栈底元素;
2. 依次读入表达式中每个字符,若是操作数则进OPND栈,若是运算符则和OPRT栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈 顶元素和当前读入的字符均为“#”)。
算法的代码实现:
OpreandType EvaluateExperession{
//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和算术栈,OP为运算符集合。
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
}//while
return GetTop(OPND);
}//EvaluateExpression
} |