目錄

前言：?

中綴表達(dá)式：

?后綴表達(dá)式：

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：

后綴表達(dá)式計(jì)算結(jié)果：

總結(jié)：?

前言：?

計(jì)算機(jī)在計(jì)算四則運(yùn)算的時(shí)候，由于括號以及運(yùn)算優(yōu)先級的存在，并不能夠很好的處理所有的運(yùn)算，為了處理這種情況，我們引入了后綴表達(dá)式來優(yōu)化算法。

中綴表達(dá)式：

????????中綴表達(dá)式是常見的數(shù)學(xué)表達(dá)式表示方法，即操作數(shù)位于操作符之間。例如，最常見的中綴算術(shù)表達(dá)式是 "3 + 4"。中綴表達(dá)式有一個(gè)顯著的特點(diǎn)，就是需要采用運(yùn)算符優(yōu)先級來確定表達(dá)式的計(jì)算順序。如果表達(dá)式中包含不同優(yōu)先級的運(yùn)算符，則需要采用約定的優(yōu)先級規(guī)則來計(jì)算表達(dá)式。在處理中綴表達(dá)式時(shí)，通常需要將表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式或前綴表達(dá)式來方便計(jì)算。

?后綴表達(dá)式：

????????逆波蘭表達(dá)式，又稱后綴表達(dá)式，是一種數(shù)學(xué)表達(dá)式的表示方法。在逆波蘭表達(dá)式中，操作符在操作數(shù)之后，因此也被稱為后綴表示法。例如，表達(dá)式 “3 + 4” 在逆波蘭表達(dá)式中表示為 “3 4 +”。逆波蘭表示法可以通過棧來實(shí)現(xiàn)，首先將所有操作數(shù)入棧，每當(dāng)遇到一個(gè)操作符時(shí)，彈出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行運(yùn)算，并將運(yùn)算結(jié)果再次壓入棧中，直到整個(gè)表達(dá)式處理完畢。與傳統(tǒng)的中綴表達(dá)式相比，逆波蘭表達(dá)式的優(yōu)點(diǎn)是可以不用考慮運(yùn)算符優(yōu)先級的問題。

后綴表達(dá)式巧妙地解決了計(jì)算機(jī)在處理數(shù)字運(yùn)算的時(shí)候難處理算數(shù)優(yōu)先級的問題。

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式：

轉(zhuǎn)化規(guī)則：從左到右遍歷中綴表達(dá)式中的每個(gè)數(shù)字和符號，如果是數(shù)字就輸出，成為后綴表達(dá)式的一部分，如果是符號，就判斷其與棧頂符號的優(yōu)先級，是右括號或優(yōu)先級不高于棧頂符號（乘除優(yōu)先于加減），則棧頂元素依次出棧并輸出，并把當(dāng)前符號進(jìn)棧，一直到最后輸出后綴表達(dá)式為止。

我們以?9+（3-1）*3+10/2?為例：

?第一步：第一個(gè)數(shù)字是9，直接輸出，第二個(gè)是+號，進(jìn)棧

?第二步：第三個(gè)符號是 '?( ' ,依然是符號，但是是左括號還沒有配對，因此進(jìn)棧，左括號之后是3，為數(shù)字直接輸出，三后面是-號，進(jìn)棧。-號后面是數(shù)字1，出棧

?第三步：數(shù)字1后面是 ‘ ）’ ,已經(jīng)滿足我們前面提到的如果是右括號就出棧，因此棧頂依次出棧輸出，直到 ‘（’ 出棧為止。

?第四步：‘）’ 后面是 ‘ * ’ 號，此時(shí)入棧的和棧頂都是符號，就要進(jìn)行比較，因?yàn)?的優(yōu)先級比+高，因此入棧，‘*’號后面是數(shù)字3，直接輸出

?第五步：數(shù)字3后面是‘ + ’號，此時(shí)棧頂?shù)?‘ * ’ 要比‘? +? ’的優(yōu)先級高，因此棧內(nèi)的元素全部出棧，‘+’號后面的是數(shù)字10，直接輸出。需要注意的是此處的+并不是9后面的+，而是3后面的+。

?第六步：10后面是‘ / ’號，直接入棧，‘ / ’號后面是2，數(shù)字就輸出，因?yàn)榇藭r(shí)這個(gè)式子已經(jīng)結(jié)束了，我們就把棧內(nèi)剩余的符號依次出棧

?這樣我們就得到了9+（3-1）*3+10/2的后綴表達(dá)式：9 3 1 - 3 * + 10 2 / +

后綴表達(dá)式計(jì)算結(jié)果：

我們?nèi)匀灰?strong>9+（3-1）*3+10/2為例，我們已經(jīng)得到了他的后綴表達(dá)式為9 3 1 - 3 * + 10 2 / +。

計(jì)算規(guī)則：從左到右遍歷表達(dá)式的每一個(gè)數(shù)字和符號，如果是數(shù)字就進(jìn)棧，如果是符號，就把處于棧頂?shù)膬蓚€(gè)數(shù)字出棧，進(jìn)行運(yùn)算，并讓計(jì)算結(jié)果再次進(jìn)棧，一直到最終獲得結(jié)果。

第一步：前三個(gè)都是數(shù)字，我們安排進(jìn)棧。

第二步：1后面是‘?- ’號，我們就將1出棧作為減數(shù)，3作為被減數(shù)，計(jì)算得到結(jié)果2，再把2返回到棧里面。再接著讓‘?- ’號后面的3進(jìn)棧。

第三步：3后面是‘ * ’號，我們就再次調(diào)出棧內(nèi)的兩個(gè)數(shù)字相乘，得到結(jié)果6，再把6入棧，在后面是‘ + ’號，就把9和6出棧相加，結(jié)果為15，再次返回棧中。

?第四步：把后面兩個(gè)數(shù)字10和2壓入棧里面，接下來是符號/，就調(diào)出棧頂?shù)?和10，10/2=5，再次把5壓入棧內(nèi)

?第五步：最后一個(gè)符號是‘ + ’號，我們就把棧頂?shù)膬蓚€(gè)元素5和15拿出來，進(jìn)行相加，把得到結(jié)果的20入棧，此時(shí)式子已經(jīng)計(jì)算完畢，就是20，就讓20出棧，作為最終運(yùn)算結(jié)果。

總結(jié)：?

? ? ? ? ?逆波蘭表達(dá)式是一個(gè)用來解決計(jì)算機(jī)識別運(yùn)算優(yōu)先級很好的思路，它是對棧的一次高級運(yùn)用，學(xué)習(xí)逆波蘭表達(dá)式可以讓我們對于棧的作用更加深刻。

今天的內(nèi)容到這里就結(jié)束了，感謝大家的閱讀。

如果我的內(nèi)容對你有幫助，請點(diǎn)贊，評論，收藏。創(chuàng)作不易，大家的支持就是我堅(jiān)持下去的動(dòng)力！

文章來源地址http://www.zghlxwxcb.cn/news/detail-539194.html

到了這里，關(guān)于【夜深人靜學(xué)數(shù)據(jù)結(jié)構(gòu)與算法 | 第二篇】后綴（逆波蘭）表達(dá)式的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！