· 以下就分"如何按后綴式進(jìn)行運(yùn)算"和"如何將原表達(dá)式轉(zhuǎn)換成后綴式"兩個問題進(jìn)行討論。
n 如何按后綴式進(jìn)行運(yùn)算？
可以用兩句話來歸納它的求值規(guī)則："先找運(yùn)算符，后找操作數(shù)。“
運(yùn)算過程為：對后綴式從左向右"掃描"，遇見操作數(shù)則暫時保存，遇見運(yùn)算符即可進(jìn)行運(yùn)算；此時參加運(yùn)算的兩個操作數(shù)應(yīng)該是在它之前剛剛碰到的兩個操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。
n 如何由原表達(dá)式轉(zhuǎn)換成后綴式？
先分析一下“原表達(dá)式”和“后綴式”兩者中運(yùn)算符出現(xiàn)的次序有什么不同。
例一. 原表達(dá)式：a×b/c×d – e+f
后綴式：a b × c / d × e – f +
例二. 原表達(dá)式：a+b×c – d/e×f
后綴式： a b c × + d e / f × –
對原表達(dá)式中出現(xiàn)的每一個運(yùn)算符是否即刻進(jìn)行運(yùn)算取決于在它后面出現(xiàn)的運(yùn)算符，如果它的優(yōu)先數(shù)"高或等于"后面的運(yùn)算，則它的運(yùn)算先進(jìn)行，否則就得等待在它之后出現(xiàn)的所有優(yōu)先數(shù)高于它的"運(yùn)算"都完成之后再進(jìn)行。
從原表達(dá)式求得后綴式的規(guī)則為：
1) 設(shè)立運(yùn)算符棧；
2) 設(shè)表達(dá)式的結(jié)束符為“#”，預(yù)設(shè)運(yùn)算符棧的棧底為“#”；
3) 若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式；
4) 若當(dāng)前字符為運(yùn)算符且優(yōu)先數(shù)大于棧頂運(yùn)算符，則進(jìn)棧，否則退出棧頂運(yùn)算符發(fā)送給后綴式；
5) 若當(dāng)前字符是結(jié)束符，則自棧頂至棧底依次將棧中所有運(yùn)算符發(fā)送給后綴式；
6) “(”對它之前后的運(yùn)算符起隔離作用，則若當(dāng)前運(yùn)算符為“(”時進(jìn)棧；
7) ")"可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符，則從棧頂起，依次退出棧頂運(yùn)算符發(fā)送給后綴式直至棧頂字符為"("止。
void transform(char suffix[ ], char exp[ ] ) {
// 從合法的表達(dá)式字符串 exp 求得其相應(yīng)的后綴式 suffix
InitStack(S); Push(S,‘#’ );
p = exp; ch = *p;
while (!StackEmpty(S)) {
if (!IN(ch, OP)) Pass( suffix, ch);
else {
switch (ch) {
case ‘(’ : Push(S, ch); break;
case ‘)’ : {
Pop(S, c);
while (c!= ‘(’ )
{ Pass( suffix, c); Pop(S, c);}
break; }
default : {
while(Gettop(S, c) && ( precede(c,ch)))
{ Pass( suffix, c); Pop(S, c); }
if ( ch!= ‘#’ ) Push( S, ch);
break;
} // defult
} // switch
} // else
if ( ch!= ‘#’ ) { p++; ch = *p; }
} // while
} // transform