中綴表達式轉後綴表達式

一、前置知識

在學習中綴表達式轉後綴表達式之前，需要先掌握以下幾個概念。

1、中綴表達式：指運算符在中間位置的表達式，例如1+2。

2、前綴表達式：指運算符在前面位置的表達式，例如+12。

3、後綴表達式：指運算符在後面位置的表達式，例如12+。

4、運算符優先級：指不同運算符之間的優先級大小，例如乘法的優先級高於加法。

二、中綴表達式轉後綴表達式的基本流程

1、從左到右掃描中綴表達式中的每一個數字或者運算符。

2、如果是數字，直接輸出到後綴表達式中。

3、如果是左括號，進棧。

4、如果是右括號，將左括號上面的運算符全部彈出棧並輸出到後綴表達式中，左右括號不輸出。

5、如果是運算符，如果它的優先級比棧頂的運算符高，將它壓入棧中。否則，將棧頂的運算符彈出，並輸出到後綴表達式中，直到該運算符的優先級大於棧頂運算符的優先級為止。

6、重複步驟1~5，直到中綴表達式掃描完畢。

7、將棧內剩餘的運算符依次彈出並輸出到後綴表達式中。

三、代碼實現

import java.util.Stack;
public class InfixToPostfix {
    public static void main(String[] args) {
        String infixExp = "(1+2)*3-4/5";
        String postfixExp = infixToPostfix(infixExp);
        System.out.println(postfixExp);
    }
    public static String infixToPostfix(String infixExp) {
        Stack operatorStack = new Stack();
        StringBuilder postfixExp = new StringBuilder();
        for (char ch : infixExp.toCharArray()) {
            if (ch >= '0' && ch <= '9') { // 判斷數字
                postfixExp.append(ch);
            } else if (ch == '(') { // 左括號直接進棧
                operatorStack.push(ch);
            } else if (ch == ')') { // 右括號彈出棧內全部運算符
                while (operatorStack.peek() != '(') {
                    postfixExp.append(operatorStack.pop());
                }
                operatorStack.pop(); // 彈出左括號
            } else { // 運算符
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(' && priority(ch) <= priority(operatorStack.peek())) {
                    postfixExp.append(operatorStack.pop());
                }
                operatorStack.push(ch);
            }
        }
        while (!operatorStack.isEmpty()) { // 棧內剩餘的運算符全部輸出
            postfixExp.append(operatorStack.pop());
        }
        return postfixExp.toString();
    }
    private static int priority(char ch) { // 運算符優先級，數字越大，優先級越高
        if (ch == '+' || ch == '-') {
            return 1;
        } else if (ch == '*' || ch == '/') {
            return 2;
        } else {
            return 0; // 括號優先級最高
        }
    }
}

四、實例演示

例如，將中綴表達式“(1+2)*3-4/5”轉換為後綴表達式如下：

1 2 + 3 * 4 5 / –

代碼運行結果如下：

1+2 -> 12+
(1+2)*3 -> 12+3*
4/5 -> 45/
(1+2)*3-4/5 -> 12+3*45/- -> 12+3*4/5-

五、總結

中綴表達式轉後綴表達式使用了棧的思想，通過將運算符依次壓入和彈出棧來實現轉換功能。在代碼實現時，需要注意運算符優先級的大小以及左右括號的處理方式。

掌握了中綴表達式轉後綴表達式的知識後，可以在實際編程中更加輕鬆地操作表達式的計算。