浮點(diǎn)型數(shù)據(jù)算術(shù)表達(dá)式求值算法研究與實現(xiàn)

楊愛麗

摘要：針對按常規(guī)輸入即中綴表達(dá)式輸入格式的算術(shù)表達(dá)式求值，提出了一種基于棧結(jié)構(gòu)的浮點(diǎn)型數(shù)據(jù)表達(dá)式求值算法。該算法考慮了算符之間的優(yōu)先級，同時也考慮了字符串形式的浮點(diǎn)數(shù)轉(zhuǎn)換成數(shù)值的問題，從而解決了程序設(shè)計語言中浮點(diǎn)型數(shù)據(jù)表達(dá)式求值的問題。

關(guān)鍵詞：表達(dá)式求值；棧；算符優(yōu)先級；浮點(diǎn)型數(shù)據(jù)

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）16-0261-02

1 背景

算術(shù)表達(dá)式一般由操作數(shù)（operand）、運(yùn)算符（operator）和界限符（delimiter）組成。操作數(shù)由數(shù)字0～9和小數(shù)點(diǎn)構(gòu)成，運(yùn)算符通常包括加、減、乘、除和括號，表達(dá)式界限符設(shè)定為“=”。由此，算術(shù)表達(dá)式的構(gòu)成可分成兩類符號：操作數(shù)和算符，其中算符包含運(yùn)算符和界限符。對于按常規(guī)輸入的表達(dá)式（即中綴表達(dá)式）的求值是程序設(shè)計語言編譯器中一個最基本的問題，也是棧的一個典型的應(yīng)用實例。該文利用棧結(jié)構(gòu)，根據(jù)算符之間的優(yōu)先關(guān)系，研究并實現(xiàn)了浮點(diǎn)型數(shù)據(jù)的算術(shù)表達(dá)式求值算法。

2 算符優(yōu)先關(guān)系的描述與實現(xiàn)

根據(jù)表達(dá)式的運(yùn)算規(guī)則：先乘除、后加減，同級運(yùn)算時先左后右，先括號內(nèi)后括號外。在運(yùn)算的每一步中，任意兩個相繼出現(xiàn)的算符θ1和θ2之間的優(yōu)先關(guān)系有以下三種情況：

θ1<θ2：θ1的優(yōu)先級低于θ2

θ1=θ2：θ1的優(yōu)先級等于θ2

θ1>θ2：θ1的優(yōu)先級高于θ2

對于加、減、乘、除、括號和等號，它們之間的優(yōu)先關(guān)系如表1所示，其中，“E”表示錯誤，即θ1和θ2不可能相繼出現(xiàn)。為方便處理，在表達(dá)式的前后分別加上一個“=”作為開始和結(jié)束符，它的優(yōu)先級最低。

表1 算符優(yōu)先關(guān)系表

[

θ1 θ2 + - * / （ ） = + > > < < < > > - > > < < < > > * > > > > < > > / > > > > < > > （ < < < < < = E ） > > > > E > > = < < < < < E = ]

由表1，對于相繼出現(xiàn)的算符θ1和θ2，它們之間的優(yōu)先關(guān)系可以歸納為以下5種情況：

1）θ1是“+”和“-”時，當(dāng)θ2是“*”、“/”和“（”時，它們的優(yōu)先級關(guān)系是“<”，其余時候它們之間的優(yōu)先關(guān)系是“>”；

2）θ1是“*”和“/”時，當(dāng)θ2是“（”時，它們之間的優(yōu)先級是“<”，其余時候是“>”；

3）θ1是“（”時，當(dāng)θ2是表達(dá)式結(jié)束符時，它們之間的優(yōu)先級關(guān)系用“E”表示，其余情況又可以分成兩種：當(dāng)θ2是“）”時，它們之間的優(yōu)先級是相同的，用“=”表示，θ2是其他字符時，它們之間的優(yōu)先關(guān)系是“<”；

4）θ1是“）”時，當(dāng)θ2是“（”時，它們之間的優(yōu)先級關(guān)系用“E”表示，θ2是其他字符時，它們之間的優(yōu)先關(guān)系是“>”；

5）θ1是表達(dá)式結(jié)束符時，當(dāng)θ2也是表達(dá)式結(jié)束符時，它們之間的優(yōu)先級是相同的，用“=”表示，其余情況又可分為兩種：當(dāng)θ2是“）”時，它們之間的優(yōu)先級關(guān)系用“E”表示，θ2是其他字符時，它們之間的優(yōu)先級關(guān)系是“<”。

這5種情況是根據(jù)θ1的值來分的，即當(dāng)θ1的值確定后，再根據(jù)θ2的值來判斷。由此，利用多分支選擇結(jié)構(gòu)可以實現(xiàn)算符之間的優(yōu)先關(guān)系。算法實現(xiàn)如下：

char Precede （char a， char b） //比較算符a，b的優(yōu)先級

{

char z；

if（（b=='+'）||（b=='-'）||（b=='*'）||（b=='/'）|| （b=='（'）||（b=='）'） ||（b=='='））

switch （a）

{

case '+'：

case '-'：

if（（b=='*'）||（b=='/'）||（b=='（'）） z='<'；

else z='>'； break；

case '*'：

case '/'：

if（b=='（'） z='<'；

else z='>'； break；

case '（'：

if（b=='='） z='E'；

else if（b=='）'） z='='；

else z='<'； break；

case '）'：

if（b=='（'） z='E'；

else z='>'； break；

case '='：

if（b=='='） z='='；

else if（b=='）'） z='E'；

else z='<'； break；

}

else z='E'；

return（z）；

}

3 字符串形式的浮點(diǎn)數(shù)轉(zhuǎn)換成數(shù)值算法

在表達(dá)式求值過程中，若連續(xù)讀到由數(shù)字和小數(shù)點(diǎn)構(gòu)成的字符串形式的浮點(diǎn)數(shù)，如“123.45”，則需要將其轉(zhuǎn)換成數(shù)值的123.45后再進(jìn)行處理。采用while循環(huán)讀取下一個字符并判斷該字符是否是'0'～'9'和'.'，若是，則將其轉(zhuǎn)換成數(shù)值型，同時，統(tǒng)計小數(shù)的位數(shù)。若小數(shù)位數(shù)為0，則可實現(xiàn)多位整數(shù)的計算；若小數(shù)位數(shù)大于0，則實現(xiàn)浮點(diǎn)數(shù)的計算。假設(shè)字符指針p已指向表達(dá)式字符串（下同），轉(zhuǎn)換算法實現(xiàn)如下：

sum=0；

count=0； //統(tǒng)計小數(shù)位數(shù)

while（*p>='0'&&*p<='9'||*p=='.'）