逆波蘭表達(dá)式又叫做后綴表達(dá)式。在通常的表達(dá)式中，二元運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，所以，這種表示法也稱為中綴表示。波蘭邏輯學(xué)家J.Lukasiewicz于1929年提出了另一種表示表達(dá)式的方法。按此方法，每一運(yùn)算符都置于其運(yùn)算對(duì)象之后，故稱為后綴表示。

逆波蘭表達(dá)式

　　逆波蘭表達(dá)式，它的語(yǔ)法規(guī)定，表達(dá)式必須以逆波蘭表達(dá)式的方式給出。逆波蘭表達(dá)式又叫做后綴表達(dá)式。這個(gè)知識(shí)點(diǎn)在數(shù)據(jù)結(jié)構(gòu)和編譯原理這兩門課程中都有介紹，下面是一些例子：

　　正常的表達(dá)式 逆波蘭表達(dá)式

　　a+b ---> a,b,+

　　a+(b-c) ---> a,b,c,-,+

　　a+(b-c)*d ---> a,b,c,-,d,*,+

　　a+d*(b-c)--->a,d,b,c,-,*,+

　　a=1+3 ---> a=1,3 +

　　http=(smtp+http+telnet)/1024 寫成什么呢？

　　http=smtp,http,telnet,+,+,1024,/?

逆波蘭表達(dá)式的用途

　　逆波蘭表達(dá)式是一種十分有用的表達(dá)式，它將復(fù)雜表達(dá)式轉(zhuǎn)換為可以依靠簡(jiǎn)單的操作得到計(jì)算結(jié)果的表達(dá)式。例如(a+b)*(c+d)轉(zhuǎn)換為ab+cd+*

逆波蘭表達(dá)式的優(yōu)勢(shì)

　　它的優(yōu)勢(shì)在于只用兩種簡(jiǎn)單操作，入棧和出棧就可以搞定任何普通表達(dá)式的運(yùn)算。其運(yùn)算方式如下：

　　如果當(dāng)前字符為變量或者為數(shù)字，則壓棧，如果是運(yùn)算符，則將棧頂兩個(gè)元素彈出作相應(yīng)運(yùn)算，結(jié)果再入棧，最后當(dāng)表達(dá)式掃描完后，棧里的就是結(jié)果。

一般算法

　　將一個(gè)普通的中序表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式的一般算法是：

　　(1)首先構(gòu)造一個(gè)運(yùn)算符棧，此運(yùn)算符在棧內(nèi)遵循越往棧頂優(yōu)先級(jí)越高的原則。

　　(2)讀入一個(gè)用中綴表示的簡(jiǎn)單算術(shù)表達(dá)式，為方便起見(jiàn),設(shè)該簡(jiǎn)單算術(shù)表達(dá)式的右端多加上了優(yōu)先級(jí)最低的特殊符號(hào)“#”。

　　(3)從左至右掃描該算術(shù)表達(dá)式，從第一個(gè)字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。

　　(4)如果不是數(shù)字，該字符則是運(yùn)算符，此時(shí)需比較優(yōu)先關(guān)系。

　　做法如下：將該字符與運(yùn)算符棧頂?shù)倪\(yùn)算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運(yùn)算符棧頂?shù)倪\(yùn)算符，則將該運(yùn)算符入棧。倘若不是的話，則將棧頂?shù)倪\(yùn)算符從棧中彈出，直到棧頂運(yùn)算符的優(yōu)先級(jí)低于當(dāng)前運(yùn)算符，將該字符入棧。

　　(5)重復(fù)上述操作(3)-(4)直至掃描完整個(gè)簡(jiǎn)單算術(shù)表達(dá)式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡(jiǎn)單算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示的簡(jiǎn)單算術(shù)表達(dá)式。

算法流程

　　下面是程序化算法流程：

　　1、建立運(yùn)算符棧stackOperator用于運(yùn)算符的存儲(chǔ)，壓入'\0'。

　　2、預(yù)處理表達(dá)式，正、負(fù)號(hào)前加0(如果一個(gè)加號(hào)（減號(hào)）出現(xiàn)在最前面或左括號(hào)后面，則該加號(hào)（減號(hào)）為正負(fù)號(hào)) 。

　　3、順序掃描表達(dá)式，如果當(dāng)前字符是數(shù)字（優(yōu)先級(jí)為0的符號(hào)），則直接輸出該數(shù)字；如果當(dāng)前字符為運(yùn)算符或括號(hào)（優(yōu)先級(jí)不為0的符號(hào)），則判斷第4點(diǎn) 。

　　4、若當(dāng)前運(yùn)算符為'('，直接入棧；

　　若為')'，出棧并順序輸出運(yùn)算符直到遇到第一個(gè)'('，遇到的第一個(gè)'('出棧但不輸出；

　　若為其它，比較stackOperator棧頂元素與當(dāng)前元素的優(yōu)先級(jí)：

　　如果 棧頂元素運(yùn)算符優(yōu)先級(jí) >= 當(dāng)前元素的優(yōu)先級(jí)，出棧并順序輸出運(yùn)算符直到 棧頂元素優(yōu)先級(jí) < 當(dāng)前元素優(yōu)先級(jí)，然后當(dāng)前元素入棧；

　　如果 棧頂元素 < 當(dāng)前元素，直接入棧。

　　5、重復(fù)第3點(diǎn)直到表達(dá)式掃描完畢。

　　6、順序出棧并輸出運(yùn)算符直到棧頂元素為'\0'。

　　int Precedence(char sign)

　　{

　　switch(sign)

　　{

　　case '+':

　　case '-':

　　return 1;

　　case '*':

　　case '/':

　　return 2;

　　case '^':

　　case '%':

　　return 3;

　　case '(':

　　case '@':

　　default:

　　return 0;

　　}

　　}

　　/****************中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 ********************/

　　void Change(char* s1,char* s2)

　　{

　　seqstack T;

　　int i=0,j=0;

　　char ch;

　　SetNull(&T);

　　Push(&T,'@');

　　ch=s1[i];

　　while(ch!='\0')

　　{

　　if(ch==' ')

　　ch=s1[++i];

　　else if(ch=='(')

　　{

　　Push(&T,ch);

　　ch=s1[++i];

　　}

　　else if(ch==')')

　　{

　　while(GetTop(&T)!='(')

　　s2[j++]=Pop(&T);

　　Pop(&T);

　　ch=s1[++i];

　　}

　　else if(ch=='+' || ch=='-' ||ch=='*' ||ch=='/' ||ch=='^' ||ch=='%')

　　{

　　char w=GetTop(&T);

　　while(Precedence(w)>=Precedence(ch))

　　{

　　s2[j++]=w;

　　Pop(&T);

　　w=GetTop(&T);

　　}

　　Push(&T,ch);

　　ch=s1[++i];

　　}

　　else

　　{

　　while((ch>='0' && ch<='9')||ch=='.')

　　{

　　s2[j++]=ch;

　　ch=s1[++i];

　　}

　　s2[j++]=' ';

　　}

　　}

　　ch=Pop(&T);

　　while(ch!='@')

　　{

　　s2[j++]=ch;

　　ch=Pop(&T);

　　}

　　s2[j++]='\0';

　　}

優(yōu)先級(jí)分類

　　優(yōu)先級(jí)分為棧內(nèi)優(yōu)先級(jí)isp(In stack priority)和棧外優(yōu)先級(jí)icp(In coming priority)。除了括號(hào)以外，其他運(yùn)算符進(jìn)棧后優(yōu)先級(jí)都升1，這樣可以體現(xiàn)在中綴表達(dá)式中相同優(yōu)先級(jí)的操作符自左向右計(jì)算的要求，讓位于棧頂?shù)牟僮鞣韧藯２⑤敵觥?

　　各運(yùn)算符及符號(hào)優(yōu)先級(jí)：

　　

操作符	#	^	*,/,%	+,-	(	)
isp	0	7	5	3	1	8
icp	0	6	4	2	8	1

轉(zhuǎn)載于:https://www.cnblogs.com/yqskj/articles/2050878.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的逆波兰表达式简单介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。