表達(dá)式求值算法
算符優(yōu)先法：
根據(jù)這個(gè)運(yùn)算優(yōu)先關(guān)系的規(guī)定來實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行的倒得。
算數(shù)四則運(yùn)算規(guī)則：
先乘除泻红，后加減；,
從左算到右屎暇；
先括號(hào)內(nèi)承桥，后括號(hào)外；
任何一個(gè)表達(dá)式都是由操作數(shù)根悼、運(yùn)算符和界限符組成的凶异，稱之為單詞。其中運(yùn)算符和界限符統(tǒng)稱為算符
算符間的優(yōu)先關(guān)系
| + | - | * | / | ( | ) | # | |
|---|---|---|---|---|---|---|---|
| + | > | > | < | < | < | > | > |
| - | > | > | < | < | < | > | > |
| * | > | > | > | > | < | > | > |
| / | > | > | > | > | < | > | > |
| ( | < | < | < | < | < | = | |
| ) | > | > | > | > | > | > | |
| # | < | < | < | < | < | = |
為了實(shí)現(xiàn)算符優(yōu)先算法挤巡，可以使用兩個(gè)工作棧剩彬。一個(gè)稱為OPTR，用以寄存運(yùn)算符矿卑；另外一個(gè)稱做OPND喉恋，用以寄存操作數(shù)或運(yùn)算結(jié)果；
算法的基本思想如下：
首先置操作數(shù)棧為空棧母廷，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素轻黑；
依次讀入表達(dá)式中的每一個(gè)字符，若是操作數(shù)則進(jìn)入OPND棧琴昆，若是運(yùn)算符和OPTR棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作氓鄙，直至整個(gè)表達(dá)式求值完畢。（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”）业舍。
求值過程：
OperandType EvaluateExpression(){
//算數(shù)表達(dá)式求值的算符優(yōu)先算法抖拦。
//設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧。
//OP為運(yùn)算符集合
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 '='://脫括號(hào)并接收下一字符
Pop(OPTR,x);
c=getchar();
break;
case '>'://退棧并將運(yùn)算結(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ùn)算符棧的棧頂運(yùn)算符與讀入的運(yùn)算符之間優(yōu)先關(guān)系的函數(shù)态罪；
Operate是進(jìn)行二元運(yùn)算的函數(shù)，如果是編譯表達(dá)式下面，則產(chǎn)生這個(gè)運(yùn)算的一組相應(yīng)指令并返回存放結(jié)果的中間變量复颈；如果是解釋執(zhí)行表達(dá)式，則直接進(jìn)行該運(yùn)算诸狭，并返回運(yùn)算結(jié)果券膀。
