關(guān)鍵字：表達(dá)式啃勉、中綴忽舟、前綴、后綴淮阐、波蘭叮阅、逆波蘭
概述
在數(shù)據(jù)結(jié)構(gòu)中，棧有一個(gè)常見的應(yīng)用就是計(jì)算機(jī)中表達(dá)式的計(jì)算泣特。
基礎(chǔ)知識
中綴表達(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è)為對象棧S1昆稿，一個(gè)為運(yùn)算符棧S2（存放運(yùn)算符）。 | 2.設(shè)置兩個(gè)空棧息拜，一個(gè)為對象棧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棧頂為右括號)别惦，掃描到的運(yùn)算符直接壓入S2；若掃描到的運(yùn)算符優(yōu)先級高于等于S2棧頂運(yùn)算符夫椭，掃描到的運(yùn)算符直接壓入S2掸掸，否則（小于時(shí)）從S2彈出元素壓入S1。直到將掃描到的運(yùn)算符壓入S2蹭秋，（2）步驟結(jié)束扰付。 | （2）掃描遇到運(yùn)算符時(shí)：若S2為空或者S2棧頂為左括號(，掃描到的運(yùn)算符直接壓入S2仁讨；若掃描到的運(yùn)算符優(yōu)先級高于S2棧頂運(yùn)算符羽莺，掃描到的運(yùn)算符直接壓入S2，否則（小于等于時(shí)）從S2彈出元素壓入S1洞豁。直到將掃描到的運(yùn)算符壓入S2盐固，（2）步驟結(jié)束。 |
| 4.掃描過程遇到括號： | 4.掃描過程遇到括號： |
| （1）遇到右括號)丈挟，直接壓入S2刁卜。 | （1）遇到左括號(，直接壓入S2曙咽。 |
| （2）遇到左括號(蛔趴，依次彈出S2元素并壓入S1，直到S2棧頂為右括號)例朱，然后丟棄這一對括號孝情。 | （2）遇到右括號)，依次彈出S2元素并壓入S1洒嗤，直到S2棧頂為左括號(箫荡，然后丟棄這一對括號。 |
| 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)先級大于等于S2棧頂運(yùn)算符即可姆打，后綴只能夠大于良姆。
- 掃描中括號判斷：前綴為右括號)，后綴為左括號(幔戏。這里很容易理解玛追，從掃描方向來直觀感受，前綴首先遇到的就是右括號)闲延，后綴首先遇到的就是左括號(痊剖。
- 棧輸出序列與最終的表達(dá)式的關(guān)系：前綴相同，后綴為逆序垒玲。
計(jì)算機(jī)求值算法總結(jié)
算法
通過一個(gè)棧進(jìn)行運(yùn)算陆馁，遇到運(yùn)算符就彈出棧頂元素和次頂元素計(jì)算。
不同點(diǎn)
運(yùn)算對象的順序：前綴為棧頂元素+運(yùn)算符+次頂元素合愈，后綴為次頂元素+運(yùn)算符+棧頂元素叮贩。
記憶方法：前綴為棧頂元素在前，后綴為棧頂元素在后佛析。
