1栅受、概念
逆波蘭表示法也叫后綴表示法，即操作符號都置于操作數(shù)的后面塔淤，逆波蘭表示法可以不用括號來標識操作符的優(yōu)先級阱飘。例如：3+4 是一個中綴表達式斥杜，轉(zhuǎn)換成逆波蘭表達式為34+ 。有人可能會想有后綴表達式沥匈，中綴表達式蔗喂，那有沒有前綴表達式呢？答案是：有前綴表達式咐熙，也叫波蘭表達式，上文中的3+4 用前綴表達式表示為+34辨萍。
2棋恼、用途
1.逆波蘭表達式中不需要括號，用戶只需按照表達式順序求值锈玉，讓堆棧自動記錄中間結(jié)果爪飘；同樣的，也不需要指定操作符的優(yōu)先級
2.機器狀態(tài)永遠是一個堆棧狀態(tài)拉背，堆棧里是需要運算的操作數(shù)师崎，棧內(nèi)不會有操作符。
3.當有操作符時就計算椅棺，因此犁罩，表達式并不是從右至左整體計算而是每次由中心向外計算一部分，這樣在復雜運算中就很少導致操作符錯誤两疚。
3床估、計算原理
逆波蘭表達式進行數(shù)據(jù)計算的時候一般分為兩步：
1.將中綴表達式轉(zhuǎn)換為后綴表達式
2.對轉(zhuǎn)換完成后的后綴表達式進行計算
例子：我們以a+b-c*(d+e) 來進行分析
3.1 將其轉(zhuǎn)換為后綴表達式
.首先我們要建立一個集合 sList 來存放例子中的數(shù)據(jù)和操作符號，一個棧opStack來存放中間的操作符號诱渤，一個集合dList 來存放最后的轉(zhuǎn)換結(jié)果丐巫。
2.從sList中取出一個元素A然后進行以下判斷：
1.如果A是數(shù)字，則直接存如dList
2.如果A是運算符勺美，則和opStack棧頂?shù)脑剡M行運算優(yōu)先級比較
1.如果A的優(yōu)先級高于棧頂運算符優(yōu)先級递胧，則將A入棧opStack
2.如果A的優(yōu)先級低于或等于棧頂運算符的優(yōu)先級，那么將棧頂?shù)脑爻鰲４嫒雂List赡茸，重復此步驟直到棧頂?shù)倪\算符優(yōu)先級低于當前運算符(或者遇到括號）,然后A入棧缎脾。
3.如果A是左括號“（”直接入棧，如果是右括號“）”占卧，則將opStack中的運算符彈出存入dList赊锚，直到彈出左括號治筒，左右括號均不存入dList，左括號永遠不會彈出舷蒲，直到遇到右括號耸袜。
4.不斷重復以上步驟直到表達式解析完成。
下面來看一下上面的具體例子:a+b-c*(d+e)
| dList | opStack | 解釋 |
|---|---|---|
| {} | {} | |
| {a} | {} | a 加入dList |
| {a} | {+} | + 入棧 |
| {a,b} | {+} | b 加入dList |
| {a,b,+} | {-} | +號出棧牲平，-號入棧 |
| {a,b,+,c} | {-} | c 加入dList |
| {a,b,+,c} | {-,*} | 因為* 的優(yōu)先級高于- 則將* 直接入棧 |
| {a,b,+,c} | {-,*,(} | 左括號直接入棧 |
| {a,b,+,c,d} | {-,*,(} | d 加入dList |
| {a,b,+,c,d} | {-,*,(,+} | + 直接入棧 |
| {a,b,+,c,d,e} | {-,*,(,+} | e 直接加入dList |
| {a,b,+,c,d,e,+} | {-,*} | 將左括號之上的符號出棧加入dList |
| {a,b,+,c,d,e,+,*,-} | {} | 將棧中的剩余元素彈出 |
將dList 中的元素輸出堤框，則得到后綴表達式：ab+cde+*-
3.2 用后綴表達式來計算結(jié)果
首先建立一個結(jié)果棧rStack，然后將dList中的元素依次取出纵柿，進行入棧操作蜈抓，如果碰到操作符就從棧中取出兩個元素進行運算，結(jié)果入棧昂儒，依次重復沟使。
下面接著看上面的例子
dList {a,b,+,c,d,e,+,*,-}
rStack
{ }
{a} //a入棧
{a,b} //b入棧
{a+b} //遇到+號，取出兩個操作數(shù)進行運算渊跋，運算結(jié)果入棧
{a+b,c}
{a+b,c,d}
{a+b,c,d,e}
{a+b,c,d+e}
{a+b,c*(d+e)}
{a+b-c*(d+e)}
計算結(jié)果：a+b-c*(d+e)
4腊嗡、鞏固練習：
寫出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波蘭表達式。
答案：
abcd*-*e+fg/hij*+k-*-
