表達式計算(expression evaluation)是程式設計語言編譯中的一個最基本問題，也是早期計算機語言研究的一項重要成果，它使得高級語言程式設計師可以使用與數學形式相一致的方式書寫表達式，如a*b+c/d-c(x+y)。計算機科學計算語言FORTRAN就因Formula Translator(公式翻譯家)而得名。
基本介紹
- 中文名：表達式計算
- 外文名：expression evaluation
- 定義：使用與數學形式一致的表達式
- 類型：中綴表達式、後綴表達式
- 系統：計算機
- 套用學科：計算機原理
組成,轉換,計算,
組成
表達式由運算元、運算符和括弧組成。表達式習慣的書寫形式是一個雙目運算符(binary operator)位於兩個運算元之間，如a+b，這類表達式稱為中綴表達式(infix expression)。除了雙目運算符外，還有單目運算符(unary operator)，如I++和一a。條件運算符是C語言中唯一的三目運算符(ternary operator)。為正確計算表達式的值，任何程式設計語言都明確規定了運算符的優先權。在C語言中，當使用括弧時，從最內層括弧開始計算；對於相鄰的兩個運算符，優先權高的先計算；如果兩個運算符的優先權相同，運算次序由結合方向決定。例如，*與/是自左向右結合的，因此，a*b/c的運算次序是先乘後除。
在中綴表達式中，運算符具有不同的優先權，並且還可以使用括弧改變運算的次序，因此運算規律比較複雜，不適於計算機求解表達式。與中綴表達式相對應的還有後綴表達式和前綴表達式。
運算符在運算元之後的表達式稱為後綴表達式。
後綴表達式的特點如下：
1、後綴表達式的運算元與中綴表達式的運算元先後次序相同，而運算符的先後次序不同；
2、後綴表達式中沒有括弧，而且運算符沒有優先權；
3、後綴表達式計算過程嚴格按照從左到右的順序進行。
從以上特點可以看出，後綴表達式比較適合計算機求解。求解後綴表達式的過程為：從左到有依次掃描後綴表達式，若遇到運算符，則對該運算符前面的連續兩個運算元用該運算符進行運算。
運算符在運算元之前的表達式稱為前綴表達式。
前綴表達式的特點與後綴表達式的特點相同，只是求解過程不同，其求解過程為：從右到左依次掃描前綴表達式，若遇到運算符，則對該運算符後面的連續兩個運算元用該運算符進行運算。
綜上所述，利用計算機求解表達式分為兩個步驟：
1、把中綴表達式轉換為後綴表達式或前綴表達式；
2、按照後綴表達式或前綴表達式的運算過程計算表達式的值。
轉換
中綴表達式轉換為後綴表達式
由後綴表達式的特點可以知道，後綴表達式的運算元與中綴表達式的運算元先後次序相同，只是運算符的先後次序不同，因此，可以利用棧來保存運算符，具體轉換過程如下：
1、設定一個存放運算符的棧(運算符棧)，並置棧頂元素為“#”。“#”作為標識表達式開始的標誌，另外在表達式的尾部添加一個“#”，把它作為標識表達式結束的標誌。
2、從左到右依次掃描表達式，每次取出一個字元(運算元、運算符和括弧均看作一個字元)。
3、若字元是運算元，則直接輸出到後綴表達式中。
4、若字元是運算符，則與棧頂運算符進行比較。如果它的優先權比棧頂運算符優先權高，則直接入棧；如果它的優先權比棧頂運算符優先權低或相等，則棧頂運算符出棧並輸出到後綴表達式中。
5、若字元是“(”，則直接入棧。
6、若字元是“)”，則判斷棧頂運算符是否為“(”。若不是，則棧頂運算符出棧，並輸出到後綴表達式中，依次進行，直至棧頂運算符為“(”，拋棄“(”和“)”。、
7、若字元是“#”，則棧頂運算符依次出棧，並輸出到後綴表達式中，直至棧頂運算符為“#”，拋棄“#”。
8、重複步驟2～7，直至表達式結束。
計算
求後綴表達式的值
由於後綴表達式不需考慮運算符的優先權，因此計算較簡單。計算過程為：從左到右依次掃描後綴表達式，遇到運算符，則與運算符前邊連續兩個運算元做運算。
由於遇到運算元時，不能立即進行計算，因此設立一個棧(運算元棧)，用於存放運算元。具體運算過程如下：
1、從左到右依次掃捕後綴表達式，每次取出一個字元；
2、若字元是運算元，則入棧；
3、若字元是運算符，則連續出棧兩個運算元，計算它們的值，然後把運算結果入棧；
4、重複步驟1～3，直至表達式結束，棧中最後一個元素即是後綴表達式的值。
