棧是一個(gè)先進(jìn)后出的一種數(shù)據(jù)結(jié)構(gòu)
對(duì)于給定一個(gè)字符串計(jì)算其值，其字符串可能有三種：前，中和后綴表達(dá)式
而對(duì)于這三種表達(dá)式應(yīng)該如何計(jì)算其值
中式表達(dá)式：（3+4）* 7-6 * 2
前綴表達(dá)式： - * + 3 4 7 * 6 2

• 1.首先從左向右壓入棧s1
• 2.從s1棧頂讀取遇到數(shù)字壓入s2，遇到操作符從s2取出兩個(gè)數(shù)字進(jìn)行運(yùn)算
• 3.重復(fù)以上操作，直到s1空，s2只有一個(gè)數(shù)字，這個(gè)數(shù)字即為結(jié)果

后綴表達(dá)式： 3 4 + 7 * 6 2 * -

• 1.從右向左壓入棧s1
• 2.從s1棧頂讀取遇到數(shù)字壓入s2，遇到操作符從s2取出兩個(gè)數(shù)字進(jìn)行運(yùn)算
• 3.重復(fù)以上操作，直到最后s2剩下的數(shù)字即為結(jié)果

中綴表達(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)算符入棧；
• （4-2） 否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的較高或相等(后綴表達(dá)式中是較高,沒(méi)有相等)或棧頂運(yùn)算符為右括號(hào)“)”，也將運(yùn)算符壓入S1；
• （4-3） 否則，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運(yùn)算符相比較；
• 5 遇到括號(hào)時(shí)：
• （5-1） 如果是右括號(hào)“)”，則直接壓入S1；
• （5-2） 如果是左括號(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á)式這里要將字符串反轉(zhuǎn)輸出,這里直接輸出即可)

中綴表達(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（注意轉(zhuǎn)換為前綴表達(dá)式時(shí)是優(yōu)先級(jí)較高或相同，而這里則不包括相同的情況)
• (4-3) 否則，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到(4-1)與S1中新的棧頂運(yùn)算符相比較
• 5.遇到括號(hào)時(shí)：
• (5-1) 如果是左括號(hào)“(”，則直接壓入S1；
• (5-2) 如果是右括號(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á)式（轉(zhuǎn)換為前綴表達(dá)式時(shí)不用逆序）