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