ZeroJudge 解題筆記：k621. [紅]括號匹配問題

作者：王一哲
日期：2025年12月1日


ZeroJudge 題目連結：k621. [紅]括號匹配問題

解題想法

自訂函式 check，輸入一行字串 s，檢查 s 之中的括號是否能配對。用堆疊 st 儲存讀到的左括號，如果讀到右括號，檢查 st 最後一項是否能與這個右括號配對，如果可以配對則移除 st 最後一項；如果不能配對則印出 Wrong，跳出函式。如果函式可以執行到最後一行，印出 Right。

Python 程式碼

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

def check(s):
    st = []
    left = ("{", "[", "(")
    right = {"}": 0, "]": 1, ")":2}
    for c in s:
        if c in "{[(":
            st.append(c)
        else:
            if st and st[-1] == left[right[c]]:
                st.pop()
            else:
                print("Wrong")
                return
    print("Right")

check(input())

C++ 程式碼

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

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

void check(string s) {
    stack<char> st;
    string left = "{[(";
    map<char, int> right = {{'}', 0}, {']', 1}, {')', 2}};
    for(char c : s) {
        if (left.find(c) != string::npos) {
            st.push(c);
        } else {
            if (!st.empty() && st.top() == left[right[c]]) {
                st.pop();
            } else {
                cout << "Wrong\n";
                return;
            }
        }
    }
    cout << "Right\n";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string line; getline(cin, line);
    check(line);
    return 0;
}