// 演算法：與 C 版相同，用堆疊。左括號壓入，右括號檢查頂端是否配對。
//        這裡用 unordered_map 把每個右括號對應到它的左括號，讓比對更乾淨。
// Algorithm: same stack idea. We use an unordered_map to map each closer to its opener,
//            which makes the matching check clean and uniform.

#include <string>
#include <stack>            // std::stack 容器 / the std::stack container
#include <unordered_map>    // std::unordered_map 雜湊表 / the hash-map container

class Solution {
public:
    bool isValid(std::string s) {
        // 雜湊表：鍵是右括號，值是對應的左括號，平均 O(1) 查詢。
        // Hash map: key = closer, value = matching opener; average O(1) lookup.
        std::unordered_map<char, char> match = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };

        std::stack<char> st;            // 存放尚未關閉的左括號 / holds the openers not yet closed

        // 範圍式 for 迴圈：依序取出 s 的每個字元；c 是字元的複本。
        // Range-for loop: iterate over each char of s; c is a copy of the character.
        for (char c : s) {
            // match.count(c) 回傳 c 是否為某個右括號的鍵（0 或 1）。
            // match.count(c) tells us whether c is a closer (a key in the map): 0 or 1.
            if (match.count(c) == 0) {
                // 不是右括號 → 是左括號 → 壓入堆疊。
                // Not a closer → it's an opener → push it.
                st.push(c);
            } else {
                // 是右括號。若堆疊為空，沒有左括號可配對 → 無效。
                // It's a closer. If the stack is empty, there's no opener to match → invalid.
                // 若頂端 st.top() 不等於這個右括號需要的左括號 match[c] → 無效。
                // If the top isn't the opener this closer needs (match[c]) → invalid.
                if (st.empty() || st.top() != match[c]) {
                    return false;
                }
                st.pop();               // 配對成功：彈出頂端 / matched: pop the top
            }
        }

        // 全部掃完後，堆疊必須為空，代表每個左括號都被正確關閉了。
        // After scanning, the stack must be empty: every opener was properly closed.
        return st.empty();
    }
};