表達式求值算法
算符優(yōu)先法：
根據(jù)這個運算優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達式的編譯或解釋執(zhí)行的。
算數(shù)四則運算規(guī)則：
先乘除，后加減；,
從左算到右；
先括號內(nèi)，后括號外；
任何一個表達式都是由操作數(shù)、運算符和界限符組成的，稱之為單詞。其中運算符和界限符統(tǒng)稱為算符
算符間的優(yōu)先關(guān)系
| + | - | * | / | ( | ) | # | |
|---|---|---|---|---|---|---|---|
| + | > | > | < | < | < | > | > |
| - | > | > | < | < | < | > | > |
| * | > | > | > | > | < | > | > |
| / | > | > | > | > | < | > | > |
| ( | < | < | < | < | < | = | |
| ) | > | > | > | > | > | > | |
| # | < | < | < | < | < | = |
為了實現(xiàn)算符優(yōu)先算法，可以使用兩個工作棧。一個稱為OPTR，用以寄存運算符；另外一個稱做OPND，用以寄存操作數(shù)或運算結(jié)果；
算法的基本思想如下：
首先置操作數(shù)棧為空棧，表達式起始符“#”為運算符棧的棧底元素；
依次讀入表達式中的每一個字符，若是操作數(shù)則進入OPND棧，若是運算符和OPTR棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)操作，直至整個表達式求值完畢。（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）。
求值過程：
OperandType EvaluateExpression(){
//算數(shù)表達式求值的算符優(yōu)先算法。
//設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧。
//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 '<'://棧頂元素優(yōu)先權(quán)低
Push(OPTR,c);
c=getchar();
break;
case '='://脫括號并接收下一字符
Pop(OPTR,x);
c=getchar();
break;
case '>'://退棧并將運算結(jié)果入棧
Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,ttheta,b));
break;
}//switch
}
}//while
return GetTop(OPND);
}//EvaluateExpression
其中，Precede函數(shù)是判定運算符棧的棧頂運算符與讀入的運算符之間優(yōu)先關(guān)系的函數(shù)；
Operate是進行二元運算的函數(shù)，如果是編譯表達式，則產(chǎn)生這個運算的一組相應(yīng)指令并返回存放結(jié)果的中間變量；如果是解釋執(zhí)行表達式，則直接進行該運算，并返回運算結(jié)果。
E5E6DC97A7925BE8033BC28BCE74A26D.jpg
