中綴表達式就是我們正常工作中寫的表達式，如 a+(b-c)*d ，編譯系統將中綴表達式改寫 abc-d*+，這種運算符在操作數后面稱為后綴表達式（也稱逆波蘭表達式）。

如何實現轉換的呢？這里做一下自己的理解及記錄。

利用棧來實現

轉換過程需要用到棧，這里用兩個棧，stack 棧用來存放運算符，post 棧用來存放最后的后綴表達式。具體規則如下：

從左到右掃描中綴表達式，若是操作數，直接存入 post 棧；

若是運算符：
（1）該運算符是左括號 ( , 則直接存入 stack 棧。
（2）該運算符是右括號 )，則將 stack 棧中 ( 前的所有運算符出棧，存入 post 棧。
（3）若該運算符為非括號，則將該運算符和 stack 棧頂運算符作比較：若高于棧頂運算符，則直接存入 stack 棧，否則將棧頂運算符出棧（從棧中彈出元素直到遇到發現更低優先級的元素(或者棧為空)為止），存入 post 棧。
（4）當掃描完后，stack 棧中還有運算符時，則將所有運算符出棧，存入 post 棧。

例子：中綴表達式 a + b * c + (d * e + f) * g，其轉換成后綴表達式則為a b c * + d e * f + g * +。

掃描stack 棧post 棧

a	空	a
a+	+	a
a+b	+	ab
a+b*	+*	ab
a+b*c	+*	abc
a+b*c+	+	abc*+
a+b*c+(	+(	abc*+
a+b*c+(d	+(	abc*+d
a+b*c+(d*	+(*	abc*+d
a+b*c+(d*e	+(*	abc*+de
a+b*c+(d*e+	+(+	abc*+de*
a+b*c+(d*e+f	+(+	abc*+de*f
a+b*c+(d*e+f)	+	abc*+de*f+
a+b*c+(d*e+f)*	+*	abc*+de*f+
a+b*c+(d*e+f)*g	+*	abc*+de*f+g
a+b*c+(d*e+f)*g#	空	abc*+de*f+g*+

注意：表格中第6步，讀到+,因為棧頂元素*的優先級高，所以*出棧，棧中下一個元素+優先級與讀到的操作符+一樣，所以也要彈出。然后再將讀到的+壓入棧中。
第13步，讀到)，則直接將棧中元素彈出直到遇到(為止。這里左括號前只有一個操作符+被彈出。

代碼實現

import java.util.Stack;public class InToPost {private Stack<Character> opStack;private Stack<Character> outStack;private String input;public InToPost(String in) {input = in;opStack = new Stack<Character>();outStack = new Stack<Character>();}public Stack<Character> doTrans() { //其他類型自行轉換for (int i = 0; i < input.length(); i++) {char ch = input.charAt(i);switch (ch) {case '+':case '-':operationOpStack(ch, 1);break;case '*':case '/':operationOpStack(ch, 2);break;case '(':opStack.push(ch);break;case ')':operationParen();break;default:outStack.push(ch);break;}}while (!opStack.isEmpty()) {outStack.push(opStack.pop());}return outStack;}public void operationOpStack(char opThis, int prec1) {//運算符棧操作while (!opStack.isEmpty()) {char opTop = opStack.pop();if (opTop == '(') {opStack.push(opTop);}else {int prec2;if (opTop == '+' || opTop == '-')prec2 = 1;elseprec2 = 2;if (prec2 < prec1) {opStack.push(opTop);break;}elseoutStack.push(opTop);}}opStack.push(opThis);}public void operationParen() {while (!opStack.isEmpty()) {char c = opStack.pop();if (c == '(') break;elseoutStack.push(c);}}public static void main(String[] args) {String input = "1+2*4/5-7+3/6";InToPost theTrans = new InToPost(input);Stack<Character> output = theTrans.doTrans(); System.out.println("Postfix is " + output + '\n');} }

利用語法樹

先將中綴表達式用二叉樹表示出來，再后序遍歷該二叉樹，就得到其相應的后綴表達式。

加括號法

加括號法先將中綴表達式每步要計算的表達式加上括號，然后將每個運算符移到其所在括號的外面，最后，從左到右去掉括號后就是后綴表達式。

例子： a+(b-c)*d

加括號 (a+((b-c)*d))移運算符 (a((bc)-d)*)+
去括號 abc-d*+

后綴表達式求值

求值過程可用棧來輔助存儲。假定待求值的后綴表達式為：6 5 2 3 + 8 * + 3 + *，則其求值過程如下：

• 遍歷表達式，遇到數字首先放入棧，此時棧如下 6 5 2 3
• 接著讀到+，則彈出3和2，執行3+2，將結果5壓棧 6 5 5
• 讀到8，壓棧 6 5 5 8
• 讀到 *, 彈出8和5，執行8*5，將結果40壓棧 6 5 40
• 讀到 +,彈出40和5，執行40+5，將結果45壓棧 6 45
• 讀到 3,壓棧 6 45 3
• 讀到 +,彈出3和45，執行3+45，將結果48壓棧 6 48
• 讀到 *,彈出48和6，執行48*6，將結果288壓棧 288
• 最后結果288

總結

以上是生活随笔為你收集整理的中缀表达式转换成后缀表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。