關(guān)鍵字：表達(dá)式、中綴、前綴、后綴、波蘭、逆波蘭
概述
在數(shù)據(jù)結(jié)構(gòu)中，棧有一個(gè)常見的應(yīng)用就是計(jì)算機(jī)中表達(dá)式的計(jì)算。
基礎(chǔ)知識(shí)
中綴表達(dá)式（我們常用的寫法，通常運(yùn)算符在中間）、前綴表達(dá)式（波蘭表達(dá)式，通常運(yùn)算符在前面）、后綴表達(dá)式（逆波蘭表達(dá)式，通常運(yùn)算符在后面）
掌握的算法
需要掌握的是：中綴→后綴、中綴→前綴、前綴→中綴、后綴→前綴，其中前綴和后綴轉(zhuǎn)換為中綴即為計(jì)算機(jī)求值的過程。
中綴轉(zhuǎn)換算法總結(jié)
比較
基本算法一致，加粗字體為需要注意的不同點(diǎn)。
| 中綴→前綴 | 中綴→后綴 |
|---|---|
| 1.從右到左掃描。 | 1.從左到右掃描。 |
| 2.設(shè)置兩個(gè)空棧，一個(gè)為對(duì)象棧S1，一個(gè)為運(yùn)算符棧S2（存放運(yùn)算符）。 | 2.設(shè)置兩個(gè)空棧，一個(gè)為對(duì)象棧S1，一個(gè)為運(yùn)算符棧S2（存放運(yùn)算符）。 |
| 3.掃描過程遇到數(shù)或者運(yùn)算符： | 3.掃描過程遇到數(shù)或者運(yùn)算符： |
| （1）遇到數(shù)直接壓入S1。 | （1）遇到數(shù)直接壓入S1。 |
| （2）掃描遇到運(yùn)算符時(shí)：若S2為空或者S2棧頂為右括號(hào))，掃描到的運(yùn)算符直接壓入S2；若掃描到的運(yùn)算符優(yōu)先級(jí)高于等于S2棧頂運(yùn)算符，掃描到的運(yùn)算符直接壓入S2，否則（小于時(shí)）從S2彈出元素壓入S1。直到將掃描到的運(yùn)算符壓入S2，（2）步驟結(jié)束。 | （2）掃描遇到運(yùn)算符時(shí)：若S2為空或者S2棧頂為左括號(hào)(，掃描到的運(yùn)算符直接壓入S2；若掃描到的運(yùn)算符優(yōu)先級(jí)高于S2棧頂運(yùn)算符，掃描到的運(yùn)算符直接壓入S2，否則（小于等于時(shí)）從S2彈出元素壓入S1。直到將掃描到的運(yùn)算符壓入S2，（2）步驟結(jié)束。 |
| 4.掃描過程遇到括號(hào)： | 4.掃描過程遇到括號(hào)： |
| （1）遇到右括號(hào))，直接壓入S2。 | （1）遇到左括號(hào)(，直接壓入S2。 |
| （2）遇到左括號(hào)(，依次彈出S2元素并壓入S1，直到S2棧頂為右括號(hào))，然后丟棄這一對(duì)括號(hào)。 | （2）遇到右括號(hào))，依次彈出S2元素并壓入S1，直到S2棧頂為左括號(hào)(，然后丟棄這一對(duì)括號(hào)。 |
| 5.重復(fù)3、4步驟直到掃描完畢。 | 5.重復(fù)3、4步驟直到掃描完畢。 |
| 6.依次彈出S2元素并壓入S1。 | 6.依次彈出S2元素并壓入S1。 |
| 7.彈出S1所有元素，輸出序列即為轉(zhuǎn)換的前綴表達(dá)式。 | 7.彈出S1所有元素，輸出序列的逆序即為轉(zhuǎn)換的后綴表達(dá)式。 |
不同點(diǎn)
- 掃描方向：前綴為右→左，后綴為左→右。
- 掃描中運(yùn)算符比較：前綴掃描的運(yùn)算符優(yōu)先級(jí)大于等于S2棧頂運(yùn)算符即可，后綴只能夠大于。
- 掃描中括號(hào)判斷：前綴為右括號(hào))，后綴為左括號(hào)(。這里很容易理解，從掃描方向來(lái)直觀感受，前綴首先遇到的就是右括號(hào))，后綴首先遇到的就是左括號(hào)(。
- 棧輸出序列與最終的表達(dá)式的關(guān)系：前綴相同，后綴為逆序。
計(jì)算機(jī)求值算法總結(jié)
算法
通過一個(gè)棧進(jìn)行運(yùn)算，遇到運(yùn)算符就彈出棧頂元素和次頂元素計(jì)算。
不同點(diǎn)
運(yùn)算對(duì)象的順序：前綴為棧頂元素+運(yùn)算符+次頂元素，后綴為次頂元素+運(yùn)算符+棧頂元素。
記憶方法：前綴為棧頂元素在前，后綴為棧頂元素在后。
