計(jì)算 9 + (3-1) * 3 + 10/2
這是一個(gè)很簡單的題目 我們心算也能很快得出答案
但是如果要用程序來實(shí)現(xiàn) 就不是很好處理了
這里面的困難就在于乘除在加減的后面 烙丛， 卻要先運(yùn)算绿聘， 而加入的括號(hào)之后就變得更加復(fù)雜
但仔細(xì)觀察后發(fā)現(xiàn)， 括號(hào)都是成對(duì)出現(xiàn)的 有左括號(hào)就一定有右括號(hào) ， 對(duì)于多重括號(hào)最終也是可以完全嵌套匹配
這用棧結(jié)構(gòu)正好合適 只要碰到左括號(hào) 咧党，就將此左括號(hào)進(jìn)棧 而后面出現(xiàn)右括號(hào)時(shí)，就讓棧頂?shù)淖罄ㄌ?hào)出棧
期間讓數(shù)字運(yùn)算 這樣，最終有括號(hào)的表達(dá)式從左到右巡查一遍 棧應(yīng)該是由空到有元素 在到完全匹配成為空棧
但對(duì)于四則運(yùn)算 荞下，括號(hào)也只是當(dāng)中的一部分 先乘除后加減使得問題依然復(fù)雜
波蘭科學(xué)家想到了一種不需要括號(hào)的后綴表達(dá)式 ， 我們也把它稱為逆波蘭
這種后綴表達(dá)式是一種新的顯示方式
我們用上面的題目來看看
正常輸血表達(dá)式 9 + (3-1) * 3 + 10/2
后綴表達(dá)式 9 3 1 - 3 * + 10 2 / +
所有的符號(hào)都是在要運(yùn)算的數(shù)字的后面出現(xiàn)
后綴表達(dá)式的計(jì)算結(jié)果
計(jì)算規(guī)則
從左到右遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào) 遇到數(shù)字就進(jìn)棧 遇到符號(hào)就將處于棧頂?shù)膬蓚€(gè)數(shù)字出棧 進(jìn)行運(yùn)算 運(yùn)算結(jié)果進(jìn)棧 一直到最終獲得結(jié)果
- 初始化一個(gè)空棧 用來對(duì)要運(yùn)算的數(shù)字進(jìn)出使用
- 表達(dá)式前三個(gè)都是數(shù)字 所以 9 3 1 進(jìn)棧
此時(shí)棧為 1 3 9 - 接下來是 - 將 1 出棧作為減數(shù) 3 出棧作為被減數(shù) 進(jìn)行運(yùn)算得到結(jié)果2 進(jìn)棧
此時(shí)棧為 2 9
4 接著是 3 進(jìn)棧
此時(shí)棧為 3 2 9
5 后面是 * 號(hào) 將3出棧作為乘數(shù) 2 出棧作為被乘數(shù) 得到結(jié)果 6 進(jìn)棧
此時(shí)棧為 6 9
6 接著是 + 將6 9 出棧 得到結(jié)果 15 進(jìn)棧
此時(shí)棧為 15
7 10 2 進(jìn)棧
此時(shí)棧為 2 10 15
8 遇見 / 2 10 出棧 得到結(jié)果5 進(jìn)棧
此時(shí)棧為 5 15
9 最后是 + 5 15 出棧得到結(jié)果 20 進(jìn)棧
此時(shí)棧為 20
表達(dá)式結(jié)束得到結(jié)果 20
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式
我們把平時(shí)所用的標(biāo)準(zhǔn)四則表達(dá)式稱為 中綴表達(dá)式
中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式規(guī)則
從左到右遍歷中綴表達(dá)式的每個(gè)數(shù)字和符號(hào) 若是數(shù)字就輸出 史飞，即成為后綴表達(dá)式的一部分
若是符號(hào) 尖昏， 則判斷其與棧頂符號(hào)的優(yōu)先級(jí) 是右括號(hào)或優(yōu)先級(jí)不高于棧頂符號(hào) 則棧頂元素依次出棧并輸出 ，并將當(dāng)前符號(hào)進(jìn)棧
還是拿 9 + (3-1) * 3 + 10/2 舉例
1 初始化一空棧
2 第一個(gè)數(shù)字是9 直接加入后綴表達(dá)式 接著是 + 進(jìn)棧
此時(shí)棧為 + 后綴表達(dá)式 9
3 左括號(hào) ( 進(jìn)棧
此時(shí)棧為 ( + 后綴表達(dá)式 9
4 3 是數(shù)字 直接加入后綴表達(dá)式
此時(shí)棧為 ( + 后綴表達(dá)式 9 3
5 - 進(jìn)棧
此時(shí)棧為 - ( + 后綴表達(dá)式 9 3
6 1 加入后綴表達(dá)式
此時(shí)棧為 - ( + 后綴表達(dá)式 9 3 1
7 ) 右括號(hào)需要去匹配 棧里的第一個(gè)左括號(hào) 并將中間符號(hào)出棧
此時(shí)棧為 + 后綴表達(dá)式 9 3 1 -
8 * 優(yōu)先級(jí)高于棧頂?shù)?+ 進(jìn)棧
此時(shí)棧為 * + 后綴表達(dá)式 9 3 1 -
9 3 是數(shù)字 直接出棧
此時(shí)棧為 * + 后綴表達(dá)式 9 3 1 - 3
10 + 優(yōu)先級(jí)低于 棧頂?shù)?* 并且棧里的+ 優(yōu)先級(jí)也不低于當(dāng)前的+ 所以 * + 出棧 + 入棧
此時(shí)棧為 + 后綴表達(dá)式 9 3 1 - 3 * +
11 10 數(shù)字 直接加入后綴表達(dá)式
此時(shí)棧為 + 后綴表達(dá)式 9 3 1 - 3 * + 10
11 / 優(yōu)先級(jí)高于 棧里的 + 進(jìn)棧
此時(shí)棧為 / + 后綴表達(dá)式 9 3 1 - 3 * + 10
12 2 是數(shù)字 直接加入后綴表達(dá)式
此時(shí)棧為 / + 后綴表達(dá)式 9 3 1 - 3 * + 10 2
13 中綴表達(dá)式已經(jīng)到了尾部 所以將棧里元素依次出棧 加入后綴表達(dá)式
此時(shí)棧為 后綴表達(dá)式 9 3 1 - 3 * + 10 2 / +
得到最終后綴表達(dá)式 9 3 1 - 3 * + 10 2 / +
