在筆試中有這么一道題目，寫出一個(gè)表達(dá)式的后綴表示形式，當(dāng)時(shí)就迷茫了，什么是后綴表達(dá)式，還真沒聽過。后來查了下原來是一種比較特殊的數(shù)學(xué)表達(dá)式，因?yàn)樵谌粘Ｉ钪杏玫牟欢?，不太了解。有三種表達(dá)式：前綴表達(dá)式、中綴表達(dá)式和后綴表達(dá)式。一般用的是中綴，比如1+1，前后綴就是把操作符移到前面和后面，下面我就來介紹一下這三種表達(dá)式。

1.前綴表示法

前綴表示法又叫波蘭表示法，他的操作符置于操作數(shù)的前面（例：+ 1 2），是波蘭數(shù)學(xué)家揚(yáng)·武卡謝維奇1920年代引入的，用于簡(jiǎn)化命題邏輯。因?yàn)槲覀円话阏J(rèn)為操作符是在操作數(shù)中間的，所以在日常生活中用的不多，但在計(jì)算機(jī)科學(xué)領(lǐng)域占有一席之地。一般的表示法對(duì)計(jì)算機(jī)來說處理很麻煩，每個(gè)符號(hào)都要考慮優(yōu)先級(jí)，還有括號(hào)這種會(huì)打亂優(yōu)先級(jí)的存在，將使計(jì)算機(jī)花費(fèi)大量的資源進(jìn)行解析。而前綴表示法沒有優(yōu)先級(jí)的概念，他是按順序處理的。
舉個(gè)例子：9-2*3這個(gè)式子，計(jì)算機(jī)需要先分析優(yōu)先級(jí)，先乘后減，找到2*3，再進(jìn)行減操作；化成前綴表示法就是：- 9 * 2 3，計(jì)算機(jī)可以依次讀取，操作符作用于后一個(gè)操作數(shù)，遇到減就是讓9減去后面的數(shù)，而跟著9的是乘，也就是說讓9減去乘的結(jié)果，這對(duì)計(jì)算機(jī)來說很簡(jiǎn)單，按順序來就行了。
再看一個(gè)復(fù)雜點(diǎn)的前綴表達(dá)式：

這是一個(gè)前綴表達(dá)式的計(jì)算過程，可以看出每次只需計(jì)算第一個(gè)滿足操作符后跟兩個(gè)操作數(shù)的式子，直到最后就是結(jié)果了。

2.中綴表示法

這也就是我們一般的表示法，他的操作符置于操作數(shù)的中間（例：1 + 2），前面也說過這種方法不容易被計(jì)算機(jī)解析，但他符合人們的普遍用法，許多編程語言也就用這種方法了。在中綴表示法中括號(hào)是必須有的，要不然運(yùn)算順序會(huì)亂掉。因?yàn)楹艹Ｓ梦乙簿筒欢嘀v了。

3.后綴表示法

后綴表示法又叫逆波蘭表示法，他的操作符置于操作數(shù)的后面（例：1 2 +），他和前綴表示法都對(duì)計(jì)算機(jī)比較友好，但他很容易用堆棧解析，所以在計(jì)算機(jī)中用的很多。他的解釋過程一般是：操作數(shù)入棧；遇到操作符時(shí)，操作數(shù)出棧，求值，將結(jié)果入棧；當(dāng)一遍后，棧頂就是表達(dá)式的值。因此逆波蘭表達(dá)式的求值使用堆棧結(jié)構(gòu)很容易實(shí)現(xiàn)，和能很快求值。
注意：逆波蘭記法并不是簡(jiǎn)單的波蘭表達(dá)式的反轉(zhuǎn)。因?yàn)閷?duì)于交換律的操作符，它的操作數(shù)寫法仍然是常規(guī)順序，如，波蘭記法“/ 6 3”的逆波蘭記法是“6 3 /”而不是“3 6 /”；數(shù)字的數(shù)位寫法也是常規(guī)順序。
為了更好的了解前綴表達(dá)式的計(jì)算過程，舉個(gè)例子：5 1 2 + 4 * + 3 -，計(jì)算過程如下

最后在棧里只有一個(gè)操作數(shù)，這就是計(jì)算結(jié)果。由此我們可以看出用堆棧是很容易解析后綴表達(dá)式的。

4.表示法間轉(zhuǎn)化

這里介紹一種簡(jiǎn)單的中綴表達(dá)式轉(zhuǎn)化前后綴表達(dá)式的方法，比如這個(gè)式子：a+b*c-(d+e)。
1.按照運(yùn)算符的優(yōu)先級(jí)對(duì)所有的運(yùn)算單位加括號(hào)
式子變成：((a+(b*c))-(d+e))。
2.1.前綴表達(dá)式，把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)前面
式子變成：-( +(a *(bc)) +(de))
去掉括號(hào)：-+a*bc+de
2.2.后綴表達(dá)式，把運(yùn)算符號(hào)移動(dòng)到對(duì)應(yīng)的括號(hào)后面
式子變成：((a(bc)* )+ (de)+ )-
去掉括號(hào)：abc*+de+-

最新評(píng)論