中綴表達式轉後綴表達式（逆波蘭表示法）完整實現

算法原理

中綴表達式（如 1+2*3）轉後綴表達式（如 123*+）便於計算機求值。使用棧存儲運算符，掃描中綴表達式：

1. 數字直接輸出。
2. 左括號入棧。
3. 右括號：彈出棧中運算符輸出直到遇到左括號。
4. 運算符：若棧頂優先級更高或相等（除右結合外），彈出輸出；然後當前運算符入棧。
5. 掃描結束，將棧中剩餘運算符輸出。

優先級：() 無優先級，+- 為 1，*/% 為 2，^ 為 3（右結合）。

Java 完整實現

import java.util.Stack;

public class InfixToPostfix {
    static class Operator {
        char ch;
        int rank;
        Operator(char c) {
            ch = c;
            if (c == '+' || c == '-') rank = 1;
            else if (c == '*' || c == '/' || c == '%') rank = 2;
            else if (c == '^') rank = 3;
        }
    }

    public static String convert(String infix) {
        StringBuilder sb = new StringBuilder();
        Stack stack = new Stack<>();
        for (char c : infix.toCharArray()) {
            if (Character.isDigit(c)) {
                sb.append(c);
            } else {
                processOperator(sb, stack, c);
            }
        }
        while (!stack.isEmpty()) sb.append(stack.pop().ch);
        return sb.toString();
    }

    private static void processOperator(StringBuilder sb, Stack stack, char c) {
        Operator op = new Operator(c);
        if (c == '(' || stack.isEmpty() || stack.peek().ch == '(') {
            stack.push(op);
            return;
        }
        if (c == ')') {
            while (!stack.isEmpty() && stack.peek().ch != '(') sb.append(stack.pop().ch);
            if (!stack.isEmpty()) stack.pop(); // 彈出 '('
            return;
        }
        while (!stack.isEmpty() && stack.peek().ch != '(' && op.rank <= stack.peek().rank) {
            sb.append(stack.pop().ch);
        }
        stack.push(op);
    }

    public static void main(String[] args) {
        String expr = "1-2*(3^6-((9-8)*6)^2*6)-8";
        System.out.println(convert(expr)); // 輸出: 1236^98-6*2^6*-*-8-
    }
}

應用場景

• 計算器核心解析模組
• 編譯器表達式處理
• 腳本引擎表達式求值

此實現支持多位數擴展（需修改掃描邏輯識別連續數字），並可輕鬆添加函數、常量支持。