Java Stack 經典應用：括號匹配算法完整實現與解析

Java Stack 經典應用：括號匹配算法完整實現與解析

利用 java.util.Stack 後進先出特性，高效解決括號匹配問題。題目要求判斷只含 ()[] 的字符串是否完全匹配。

算法核心邏輯

1. 掃描字符串，遇到左括號 ( [ → 入棧
2. 遇到右括號 ) ] → 檢查棧頂： - 棧空 → 不匹配 - 棧頂非對應左括號 → 不匹配 - 匹配 → 出棧
3. 掃描結束，棧非空 → 不匹配 (有剩餘左括號)

完整代碼實現

package com.day1;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        String[] arr = new String[n];
        for (int i = 0; i < arr.length; i++) arr[i] = input.next();
        for (String s : arr) System.out.println(isMatch(s));
    }

    private static String isMatch(String str) {
        Stack stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == '(' || c == '[') {
                stack.push(c); // 左括號入棧
            } else { // 右括號
                if (stack.empty() || !isBracketMatch(stack.peek(), c)) {
                    return "No"; // 棧空或不匹配
                }
                stack.pop(); // 匹配出棧
            }
        }
        return stack.empty() ? "Yes" : "No"; // 最終檢查
    }

    private static boolean isBracketMatch(Character left, Character right) {
        return (left == '(' && right == ')') || (left == '[' && right == ']');
    }
}

Stack 關鍵 API 速查

測試用例驗證

擴展應用場景

• 編譯器語法分析：關鍵字/大括號/分號匹配
• 表達式求值：中綴轉後綴 (逆波蘭表達式)
• 瀏覽器前進/後退：雙棧實現歷史導航
• 撤銷/重做 (Undo/Redo) ：命令模式棧
• 深度優先搜索 (DFS) ：圖/樹遍歷

現代 Java 建議

💡 Stack 繼承 Vector 同步開銷大，推薦使用 Deque<T> stack = new ArrayDeque<>() 替代，提供 push/pop/peek 同樣語義，性能更優、非線程安全適用單線程場景。