ZeroJudge 解題筆記：b304. 00673 - Parentheses Balance

作者：王一哲
日期：2026年1月18日


ZeroJudge 題目連結：b304. 00673 - Parentheses Balance

解題想法

先用字典儲存 3 種右括號對應的左括號，這樣在檢查括號是否成對時比較方便。先讀取一行測資，再依序讀取這行測資中的每個字元，如果是左括號就存入堆疊 st 之中，如果讀到右括號，檢查堆疊最上面是否為對應的左括號，如果成對就移除這筆資料，如果堆疊是空的或不是對應的左括號，無解，中止迴圈。最後再檢查堆疊是否還有資料，如果有，無解。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

left = {')': '(', ']': '['}  # 左、右括號配對
n = int(input())  # n 組測資
for _ in range(n):  # 執行 n 次
    s = list(input())  # 字串轉成串列
    st = []  # 左括號堆疊
    flag = True  # 是否有解
    for c in s:  # 依序由 s 讀取字元 c
        if c in "([": st.append(c)  # 如果 c 是左括號放入堆疊
        else:  # 反之為右括號
            if not st or st[-1] != left[c]:  # 如果 st 是空的或是最後一項無法與 c 配對
                flag = False  # 無解
                break  # 中止迴圈
            else: st.pop() # 有解，移除 st 最後一項
    if st: flag = False  # 如果有剩下的左括號，無解
    print("Yes" if flag else "No")

C++ 程式碼

使用時間約為 2 ms，記憶體約為 336 kB，通過測試。

#include <iostream>
#include <string>
#include <stack>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    map<char, char> left = {{')', '('}, {']', '['}};  // 左、右括號配對
    int n; cin >> n; cin.ignore(); // n 組測資
    for(int i=0; i<n; i++) {  // 執行 n 次
        string s; getline(cin, s);  // 字串
        if (s == "\n") {  // 空白字串，有解
            cout << "Yes\n";
            continue;
        }
        stack<char> st;  // 左括號堆疊
        bool flag = true;  // 是否有解
        for(char c : s) {  // 依序由 s 讀取字元 c
            if (c == '(' || c == '[') {  // 如果 c 是左括號放入堆疊
                st.push(c);
            } else {  // 反之為右括號
                if (st.empty() || st.top() != left[c]) {  // 如果 st 是空的或是最後一項無法與 c 配對
                    flag = false;  // 無解
                    break;  // 中止迴圈
                } else{  // 有解，移除 st 最後一項
                    st.pop();
                }
            }
        }
        if (!st.empty()) flag = false;  // 如果有剩下的左括號，無解
        cout << (flag ? "Yes\n" : "No\n");
    }
    return 0;
}