Java 資料結構與演算法：中綴表達式轉後綴表達式完整實作指南

前言

在 Java 資料結構與演算法的學習中，中綴表達式轉後綴表達式（逆波蘭表示法）是經典且重要的課題。中綴表達式符合人類閱讀習慣（如 A + B），但電腦解析較為複雜；後綴表達式則適合機器運算，透過堆疊即可高效求值。本文將詳細解析轉換原理，並提供完整的 Java 實作代碼。

核心原理：戴克斯特拉演算法

中綴轉後綴的核心演算法由艾茲赫爾·戴克斯特拉提出，主要步驟如下：

1. 掃描中綴表達式的每個字元
2. 若為運算元（數字/變數），直接輸出
3. 若為左括號 (，壓入堆疊
4. 若為右括號 )，彈出堆疊直到遇到左括號
5. 若為運算子，比較優先級：
   - 堆疊為空或堆疊頂為左括號 → 直接壓入
   - 當前運算子優先級高於堆疊頂 → 直接壓入
   - 否則彈出堆疊頂運算子輸出，重複比較
6. 掃描結束後，將堆疊剩餘運算子依序彈出輸出

運算子優先級定義

完整 Java 實作代碼

// 堆疊實作
public class StackX {
    private int top;
    private char[] stackArray;
    private int maxSize;

    public StackX(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1;
        stackArray = new char[this.maxSize];
    }

    public void push(char item) { stackArray[++top] = item; }
    public char pop() { return stackArray[top--]; }
    public char peek() { return stackArray[top]; }
    public boolean isEmpty() { return (top == -1); }
    public int size() { return top + 1; }
}

// 中綴轉後綴核心類
public class InToPost {
    private StackX stack;
    private String input;
    private String output = "";

    public InToPost(String input) {
        this.input = input;
        stack = new StackX(input.length());
    }

    public String doTrans() {
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            switch (ch) {
                case '+': case '-': getOp(ch, 1); break;
                case '*': case '/': getOp(ch, 2); break;
                case '(': getOp(ch, 3); break;
                case ')': getOp(ch, 4); break;
                default: output += ch; // 運算元直接輸出
            }
        }
        while (!stack.isEmpty()) {
            output += stack.pop();
        }
        return output;
    }

    private void getOp(char op, int prec) {
        char topOp;
        if (stack.isEmpty() || prec == 3) {
            stack.push(op);
        } else if (prec == 4) { // 遇到右括號
            while (!stack.isEmpty()) {
                topOp = stack.pop();
                if (topOp == '(') break;
                output += topOp;
            }
        } else if (prec == 1) { // + -
            topOp = stack.peek();
            if (topOp == '(') stack.push(op);
            else { output += stack.pop(); stack.push(op); }
        } else { // * /
            topOp = stack.peek();
            if (topOp == '(' || topOp == '+' || topOp == '-') stack.push(op);
            else output += stack.pop();
        }
    }
}

// 測試類
public class TestInToPost {
    public static void main(String[] args) {
        String expr = "((A+B)*C)-D";
        InToPost translator = new InToPost(expr);
        System.out.println("中綴: " + expr);
        System.out.println("後綴: " + translator.doTrans());
        // 輸出: AB+C*D-
    }
}

執行結果分析

輸入 ((A+B)*C)-D，轉換過程如下：

• A、B 直接輸出 → AB
• + 進堆疊
• 遇到 ) 彈出 + → AB+
• * 進堆疊
• C 輸出 → AB+C
• ) 彈出 * → AB+C*
• - 進堆疊
• D 輸出 → AB+C*D
• 最後彈出 - → AB+C*D-

已知限制與改進方向

本實作為教學示範版本，存在以下限制：

• 僅支援單字元運算元（如 A、1），不支援多位數或變數名
• 未處理空白字元
• 缺乏錯誤處理（如括號不匹配、非法字元）
• 未支援一元運算子（如負號）

生產環境建議使用 ScriptEngine 或成熟庫（如 exp4j、JEP）處理複雜表達式解析。

總結

中綴轉後綴是編譯原理與資料結構的基石應用。掌握堆疊對運算子優先級的管理邏輯，不僅能解決表達式求值問題，更能深入理解編譯器前端的語法分析機制。建議讀者嘗試擴展支援多位數、函數呼叫等特性，以鞏固演算法功力。