国产白丝在线,日本在线视频不卡,欧美成人激情视频

中綴和后綴算術表達式的分析比較

劉愛貴

（高能物理研究所計算中心　北京　2003年）

摘要：表達式求值是程序設計語言編譯中的一個最基本問題。與人們習慣的中綴表示的表達式相比，后綴表達式不存在括號，沒有優先級的差別，表達式中各個運算是按照運算符出現的順序進行的。因此非常適合串行工作的計算機處理方式。本文首先對這兩種表達式表示方法進行了分析比較，然后通過具體分析實現這兩種表達式求值的算法來論證表達式后綴表示優于中綴表示。最后簡要談了一下中綴表達式到后綴表達式的轉換。

關鍵詞 ：中綴表達式后綴表達式前綴表達式優先級算符優先堆棧表達式轉換時間復雜度

表達式求值是程序設計語言編譯中的一個最基本問題。通常書寫的算術表達式是由操作數和運算符以及改變運算次序的圓括號連接而成的式子。運算符包括單目運算符和雙目運算符兩類，單目運算符只要求一個操作數，并被放在該操作數的前面，雙目運算符要求有兩個操作數，其位置因表示方法不同而有所差異。按照運算符與運算對象的位置關系，算術表達式的表示方法分為前綴表達式、中綴表達式和事綴表達式三種，其中后兩者較為常用。為了簡便起見，在本文的討論中只考慮雙目運算符（僅＋、－、＊、 / 　四種）以及括號。

中綴算術表達式最為常用，其二元運算符置于與之相關的兩個運算對象之間。對中綴表達式的計值，并非按照運算符出現的自然順序來執行其中的各個運算，而是根據算符間的優先關系來確定運算的次序，此外，還需要顧及括號規則。 中綴表達式的計算比較復雜，它必須遵守以下三條規則 ^[1] ：

(1) 先計算括號內，后計算括號外；

(2) 在無括號或同層括號內，先乘除運算，后加減運算，即乘除運算的優先級高于加減運算的優先級；

(3) 同一優先級運算，從左向右依次進行。

從這三條規則可以看出，在中綴表達式的計算過程中，既要考慮括號的作用，又要考慮運算符的優先級，還要考慮運算符出現的先后次序。因此，各運算符實際的運算次序往往同它們在表達式中出現的先后次序是不一致的，是不可預測的。中綴算術表達式符合人的思維方式，我們憑直觀判別一個中綴表達式中運算符運算順序并不困難，但對于計算機處理起來就比較復雜了。由于傳統計算機一維的計算模型，只能一個字符一個字符地掃描，要想得到哪一個運算符先算，就必須對整個中綴表達式掃描一遍，一個中綴表達式中有多少個運算符，原則上就得掃描多少遍才能計算完畢，這樣算法的時間復雜性就差了，顯然是不可取的。

波蘭邏輯學家 J.Lukasiewicz 于 1929 年提出了后綴表達式的表示方法。這種方法的算術表達式中的每一個運算符都置于其運算對象之后，表達式中各個運算是按照運算符出現的順序進行的，故無須使用括號來指示運算順序，因而又稱為無括號式。 ^[2] 如中綴表達式 100+(200-50*3)/(13-8) ，其后綴表達式為 100 200 50 3 * - 13 8 - / + 。在后綴表達式中，不存在括號，也不存在優先級的差別，計算過程完全按照運算符出現的先后次序進行，整個計算過程僅需一遍掃描便可完成，顯然比中綴表達式的計算要簡單得多。其實 J.Lukasiewicz 原來提出的是表達式的前綴表示方法，即把每一運算符置于運算對象之前 ^[2] , 前面的表達式用前綴表示為 + 100 * 50 3 - / 200 20 。前綴表達式的優點與后綴表達式的相同，也不含有括號，表達式中的運算也是按照運算符出現的順序進行的，計值也很容易實現。但由于其表示方法與人們的習慣相差甚遠，因而并不常用。

對于簡單的中綴表達式我們很容易得到其后綴表達式，但對于較為復雜的中綴表達式就很難從直觀上得到其后綴表達式。我們可以用一棵二叉樹來表示算術表達式，內部結點表示運算符，葉結點代表運算對象，如 100+(200-50*3)/(13-8) 。這樣按照先序、中序、后序遍歷二叉樹，就可以分別得到前綴、中綴和后綴算術表達式。如此可以很方便地實現三種算術表達式的相互轉換。

二叉樹表示的算術表達式 100+(200-50*3)/(13-8)

在計算機中進行算術表達式的計算是通過堆棧來實現的。后綴表達式由于其本身所具有的優點，表達式中各個運算是按照運算符出現的順序進行的 , 其計算求值比較簡單，掃描一遍即可完成。它只需要使用一個棧，用來存儲后綴表達式中的操作數、計算過程中的中間結果以及最后結果。后綴表達式求值算法的基本思路是：把包含后綴算術表達式的字符串定義為一個輸入字符串，按順序從中讀取字符（空格作為數據之間的分隔符，不會被作為字符讀入）時，若是運算符，則表明它的兩個操作數已在棧中，其中棧頂元素為運算符的后一個操作數，棧頂元素的下一個元素為運算符的前一個操作數，把兩個操作數出棧進行相應運算即可，然后把運算結果再壓入棧中；否則，讀入的字符必為操作數字符串中的字符，讀取整個操作數字符串，轉換成數后并把它壓入到棧中。依次掃描每一個字符并進行上述處理，直到遇到結束符 ’ # ’ 為止，表明后綴表達式計算完畢，最終結果保存在棧中，并且棧中僅存這一個值，把它彈出返回即可。后綴表達式求值算法描述為：

int postexpression(char *exp)

{

stack<int> *opnd=new(stack<int>);// 操作數棧

char ch=*exp;

int x=0,y,z,flag=FALSE;

int result;

while(ch!='#')

{

if(!Operator(ch)) // 如果當前字符不是運算符

{

if(ch!=' ')

{

x=x*10+(int)(ch)-48; // 計算操作數

flag=TRUE;

}

else

{

if(flag)opnd->push(x); // 操作數入棧

x=0;

flag=FALSE;

}

else // 當前字符為運算符，兩個操作數出棧，計算并將結果入棧

{

x=opnd->pop();

y=opnd->pop();

z=calc(y,ch,x);

opnd->push(z);

}

ch=*(++exp); // 取下一字符

}

result=opnd->pop();

return(result);

}

此算法的運行時間主要花在 while 循環上，它從頭到尾掃描后綴表達式中的每一個數據（每個操作數或運算符均為一個數據），若后綴表達式由 n 個數據組成，則此算法的時間復雜度為 O(n) 。此算法在運行時所占用的臨時空間主要取決于操作數棧的大小，顯然，它的最大深度不會超過表達式中操作數的個數，因為操作數的個數與運算符（假定把 ’ # ’ 也看作為一個特殊運算符，即結束運算符）的個數相等，所以此算法的空間復雜度也同樣為 O(n) 。

中綴表達式求值同樣用堆棧來實現，但實現相對后綴表達式較為復雜，它采用一種稱為“算符優先法”的算法 ^[1] ，它必須嚴格按照前面所述的三條規則來進行計算。為了實現算符優先算法，要使用兩個工作棧。一個稱為 OPTR, 用以寄存運算符；另一個稱為 OPND ，用以寄存操作數或運算結果，它的基本思想于后綴表達式計算的不同在于：當讀取到運算符時并不可能作相應運算，必須先比較運算符棧中棧頂元素與當前運算符的優先級。若為‘ < ’則運算符入棧；若為‘ = ’則說明是一對括號，需脫括號；若‘ > ’則作相應運算并將結果入棧。

中綴表達式求值算法描述如下：

int middexpression(char *exp)

{

stack<int> *opnd=new(stack<int>); // 操作數棧

stack<char> *optr=new(stack<char>); // 運算符棧

char ch=*exp;

int x=0,y,z;

int result;

optr->push('#');

while(ch!='#'||optr->gettop()!='#')// 字符掃描完畢且運算符棧僅有‘＃’時運算結束

{

if(!Operator(ch)) // 取操作數并入棧

{

x=x*10+(int)(ch)-48;

if(Operator(*(exp+1)))

{

opnd->push(x);

x=0;

}

ch=*++exp;

}

else

{

switch(Precede(optr->gettop(),ch))

{

case '<':// 棧頂元素優先權低

optr->push(ch);

ch=*++exp;

break;

case '=':// 脫括號并接收下一字符

optr->pop();

ch=*++exp;

break;

case '>':// 退棧并將運算結果入棧，但不取下一表達式字符

x=opnd->pop();

y=opnd->pop();

z=calc(y,optr->pop(),x);

opnd->push(z);x=0;

break;

}

result=opnd->pop();

return(result);

}

分析上面算法，運算時間主要用在字符串掃描和算符優先權的比較上。把 # 看作運算符，操作數與運算符個數相同，最壞情況下優先級比較是 n/2 次，即運算順序完全是逆序的 , 每個字符掃描一遍是 O(n) 的，所以整個算法復雜度是 O(n ² ) 的。算法中用到兩個棧，分別為 O(n/2) ，其算法空間復雜度是 O(n) 的。

從兩個算法的分析比較中，我們可以看到優先級的比較、運算不按順序進行使中綴表達計算的時間復雜性從 O(n) 降到了 O(n ² ), 花費了大量的運行時間。在 Pentium II 266MHz 、 128M RAM 、 Win2000 、 Vc6.0 測試環境下 , 對中綴表達式 100+(200-(50*(8-45/9))) 、 17*9/3+13-11 、 100+(200-50*3)/(13-8) 和其后綴表達式表達 100 200 50 8 45 9 / - * - + 、 17 9 * 3 / 13 + 11 – 和 100 200 50 3 * - 13 8 - / + 分別調用 middexpression() 和 postexpression() ，三個表達式運算時間 ( 秒 ) 分別為（ 0.008681,0.003974 ）、（ 0.005812,0.003663 ）、（ 0.008437,0.004524 ）。第一個表達式中綴表示運算是完全逆序的，其運算時間與后綴表示運算時間之比為 2.184332 ： 1 ；第二個表達式中綴表示運算是完全順序的，其運算時間與后綴表示運算時間之比為 1.586667 ： 1 ；第三個表達式中綴表達運算是一般情況，其運算時間與后綴表示運算時間之比為 1.865047 ： 1 。從中我們發現，后綴表達式運算時間比較穩定，而中綴表達式由于運算順序不同運行時間相差較大。可見在時間復雜度和效率方面后綴表示方法要明顯優于中綴表示方法。

經以上的分析比較可以發現，后綴表達式要優于中綴表達式，非常適合用計算機求解。但是比起中綴表達式，形式上沒有中綴表達直觀，后者更適于人類的思維方式。因此利用計算機進行科學計算，在高級語言程序設計中我們用中綴表達式來表示，而在計算機內部是用后綴表達式來進行計算的，因此為了處理方便，編譯程序常把中綴表達式首先轉換為后綴表達式然后再進行運算。中綴表達式－后綴表達式轉換算法的思想與中綴表達式求值算法基本相似，這里就不再贅述。但值得一提的是，轉換的時間復雜度是 O （ n ）的，且只需要一個 O(n/2) 的運算符棧。利用表達式的后綴表示和堆棧技術只需要兩遍掃描就可完成中綴算術表達式的計算，時間復雜度仍是 O(n) 的，顯然要大大優于直接進行中綴算術表達式計算。

[ 參考文獻 ]

[1] 、嚴蔚敏、吳偉民　　　　數據結構 1997.7 清華大學出版社

[2] 、蔣立源　　　　　　　　編譯原理　　　　 1 993.8 西北工業大學出版社

中綴和后綴算術表達式的分析比較

更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

2元

5元

10元

20元

自定義

欧美三区_成人在线免费观看视频_欧美极品少妇xxxxⅹ免费视频_a级毛片免费播放_鲁一鲁中文字幕久久_亚洲一级特黄