算術表達式求值朱亮

1、 算術表達式求值算法解析 2007級4班 2009年11月25日1 棧的應用算術表達式求值 表達式求值是程序設計語言編譯中的一個最基本問題。它的實現(xiàn)方法是棧的一個典型的應用實例。 表達式都是由操作數(shù)（operand）、運算符（operator）和界限符（delimiter）組成的。其中操作數(shù)可以是常數(shù)，也可以是變量或常量的標識符；運算符是算術運算符（ + , - , * , / ）；界限符為左右括號和標識表達式結束的結束符。2算術表達式的表示方法1. 中綴表達式運算符在操作數(shù)之間如： A * B / C 運算規(guī)則：(1) 先計算括號內，后計算括號外；(2) 在無括號或同層括號內，先進行乘除運算

2、，后進行加減運算，即乘除運算的優(yōu)先級高于加減運算的優(yōu)先級；(3) 同一優(yōu)先級運算，從左向右依次進行。3用計算機來處理中綴表達式比較復雜。一個中綴表達式中有多少個運算符，原則上就得對表達式掃描多少遍，才能完成計算。在編譯系統(tǒng)中，把中綴表達式轉換成另外一種表示方法，即后綴表達式，然后對后綴式表達式進行處理，后綴表達式也稱為逆波蘭式。 4 2. 后綴表達式： 1929 年，由波蘭邏輯學家（Lukasiewicz）提出。例 A * B / C; A B * C / ; 定義：運算符緊跟在兩個操作數(shù)之后的表達式叫后綴 表達式。 優(yōu)點： 后綴表達式沒有括號 不存在優(yōu)先級的差別 計算過程完全按照運算符出現(xiàn)的

3、先后次序 進行 5 后綴表達式求值的方法： 從左到右讀入后綴表達式，若讀到的是操作 數(shù)，將它壓入堆棧。 若讀到的是運算符，就從堆棧中連續(xù)彈出兩 個元素，進行相應的運算，并將結果壓入棧 中。 讀入結束符時，棧頂元素就是計算結果。6 中綴表達式 后綴表達式 a+b a b+ a+b*c a b c *+ a*b*c+c*d a b * c * c d * + (a+b)*(c-d)*e+f) a b + c d e * f + * 例 計算后綴表達式ABC*/DE*+AC*-; 7操作 后綴表達式 棧T2 =A/T1 T2 DE*+AC*- =; T2 DET3 =D*E T2T3 +AC*- =

4、; T2 T3 T4=T2+T3 T4AC*- =; T4ACT5 =A*C T4 T5 - =; T4 T5 T6 =T4- T5 =; T6T1=B*C AT1/DE*+AC*- =; AT1 ABC*/DE*+AC*- =; ABC8后綴表達式求值的ADL算法：算法EPE ( p, n )EPE1 初始化CREATS ( S ) .EPE2 表達式求值FOR i=1 TO n DO IF NOT ( ISOPTOR( P i ) THEN S P i ELSE ( y S . x S. S APPLIED(P i , x , y) ) 9中綴表達式轉換成后綴表達式首先設定一個運算符棧，用

5、來保存掃描中綴表達式得到的暫不能放入后綴表達式中的運算符?；舅枷耄簭淖蟮接乙来巫x出中綴表達式中的各個符號（操作數(shù)或運算符），每讀出一個符號后，根據(jù)如下運算規(guī)則進行處理：1. 假如是操作數(shù)，將其放入后綴表達式中；2. 如果是運算符，則： （1） ?？眨哼\算符放入棧中， （2） 棧不空：比較當前讀到的運算符與棧頂運算符的優(yōu)先級10 1）假如讀出的運算符的優(yōu)先級大于棧頂運算符的優(yōu)先級，則將其壓入運算符棧，讀中綴表達式的下一個符號。 2）若棧頂運算符的優(yōu)先級比讀到的運算符的優(yōu)先級高或二者相等，彈出棧頂運算符放入后綴表達式中，當前讀到的運算符入棧； 3）遇到“（”，壓入堆棧； 4）遇到“）”，把“（”上面的操作符依次彈出加到后綴表達式中，“（”出棧； 3. 假如讀出的是表達式結束符“#”，棧中剩余的運算符依次出棧并寫入到后綴表達式中，轉換完成。11將(A+B)*(C-D)*E+F)轉換成后綴表達式 AB+CD-E*F+*12(A+B)*(C-D)*E+F)棧 輸出序列 （ A （ A B A B *( A B C *(- A B CD *( A B CD- *(* A B CD- E *( A B CD- E* *( A B CD- E*F * A B CD- E*F+ A B CD- E*F+ *13