算術(shù)表達(dá)式求值朱亮

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

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

3、先后次序 進(jìn)行 5 后綴表達(dá)式求值的方法： 從左到右讀入后綴表達(dá)式，若讀到的是操作 數(shù)，將它壓入堆棧。 若讀到的是運(yùn)算符，就從堆棧中連續(xù)彈出兩 個(gè)元素，進(jìn)行相應(yīng)的運(yùn)算，并將結(jié)果壓入棧 中。 讀入結(jié)束符時(shí)，棧頂元素就是計(jì)算結(jié)果。6 中綴表達(dá)式 后綴表達(dá)式 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 + * 例 計(jì)算后綴表達(dá)式ABC*/DE*+AC*-; 7操作 后綴表達(dá)式 棧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后綴表達(dá)式求值的ADL算法：算法EPE ( p, n )EPE1 初始化CREATS ( S ) .EPE2 表達(dá)式求值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中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式首先設(shè)定一個(gè)運(yùn)算符棧，用

5、來保存掃描中綴表達(dá)式得到的暫不能放入后綴表達(dá)式中的運(yùn)算符。基本思想：從左到右依次讀出中綴表達(dá)式中的各個(gè)符號(hào)（操作數(shù)或運(yùn)算符），每讀出一個(gè)符號(hào)后，根據(jù)如下運(yùn)算規(guī)則進(jìn)行處理：1. 假如是操作數(shù)，將其放入后綴表達(dá)式中；2. 如果是運(yùn)算符，則： （1） ?？眨哼\(yùn)算符放入棧中， （2） 棧不空：比較當(dāng)前讀到的運(yùn)算符與棧頂運(yùn)算符的優(yōu)先級(jí)10 1）假如讀出的運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)，則將其壓入運(yùn)算符棧，讀中綴表達(dá)式的下一個(gè)符號(hào)。 2）若棧頂運(yùn)算符的優(yōu)先級(jí)比讀到的運(yùn)算符的優(yōu)先級(jí)高或二者相等，彈出棧頂運(yùn)算符放入后綴表達(dá)式中，當(dāng)前讀到的運(yùn)算符入棧； 3）遇到“（”，壓入堆棧； 4）遇到“）”，把“（”上面的操作符依次彈出加到后綴表達(dá)式中，“（”出棧； 3. 假如讀出的是表達(dá)式結(jié)束符“#”，棧中剩余的運(yùn)算符依次出棧并寫入到后綴表達(dá)式中，轉(zhuǎn)換完成。11將(A+B)*(C-D)*E+F)轉(zhuǎn)換成后綴表達(dá)式 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