中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
后綴表達(dá)式適合計(jì)算機(jī)進(jìn)行運(yùn)算,但是人卻不太容易寫(xiě)出來(lái),尤其是表達(dá)式很長(zhǎng)的情況下,因此在開(kāi)發(fā)中,我們需要將中綴表達(dá)式轉(zhuǎn)成后綴表達(dá)式。
具體步驟如下:
1.初始化兩個(gè)棧:運(yùn)算符棧s1和儲(chǔ)存中間結(jié)果的棧s2
2.從左至右掃描中綴表達(dá)式
3.遇到操作數(shù)時(shí),將其壓s2
4.遇到運(yùn)算符時(shí),比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí):
4.1 如果s1為空,或棧頂運(yùn)算符為左括號(hào)"(",則直接將此運(yùn)算符入棧
4.2 否則,若優(yōu)先級(jí)比棧頂運(yùn)算符高,也將運(yùn)算符壓入s1
4.3 否則,將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中,再次轉(zhuǎn)到(4.1)與s1中新的棧頂運(yùn)算符相比較
5.遇到括號(hào)時(shí):
- 如果是左括號(hào)"(",則直接壓入s1
- 如果是右括號(hào)")",則依次彈出s1棧頂?shù)倪\(yùn)算符,并壓入s2,直到遇到左括號(hào)為止,此時(shí)將一對(duì)括號(hào)丟棄
6.重復(fù)步驟2至5,直到表達(dá)式的最右邊
7.將s1中剩余的運(yùn)算符依次彈出并壓入s2
8.依次彈出s2中的元素并輸出,結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式
中綴表達(dá)式1 + (( 2 + 3 ) x 4 ) - 5 ===>>后綴表達(dá)式
將s2出棧- 5 + x 4 + 3 2 1 ===>> 1 2 3 + 4 x + 5 -
| 掃描到的元素 | s2(棧底->棧頂) | s1(棧底->棧頂) | 說(shuō)明 |
|---|---|---|---|
| 1 | 1 | 空 | 數(shù)字,直接入棧 |
| + | 1 | + | s1為空,直接入棧 |
| ( | 1 | +( | 左括號(hào),直接入棧 |
| ( | 1 | +(( | 左括號(hào),直接入棧 |
| 2 | 12 | +(( | 數(shù)字,直接入棧 |
| + | 12 | +((+ | s1棧頂為左括號(hào),運(yùn)算符直接入棧 |
| 3 | 123 | +((+ | 數(shù)字,直接入棧 |
| ) | 123+ | +( | 右括號(hào),彈出運(yùn)算符直至遇到左括號(hào) |
| x | 123+ | +(x | s1棧頂為左括號(hào),運(yùn)算符直接入棧 |
| 4 | 123+4 | +(x | 數(shù)字,直接入棧 |
| ) | 123+4x | + | 右括號(hào),彈出運(yùn)算符直至遇到左括號(hào) |
| - | 123+4x+ | - | -與+優(yōu)先級(jí)相同,因此彈出+,再壓入- |
| 5 | 123+4x+5 | - | 數(shù)字,直接入棧 |
| 到達(dá)右端 | 123+4x+5- | 空 | s1中剩余的運(yùn)算符 |
