// 演算法：用堆疊。遇到左括號就壓入，遇到右括號就檢查堆疊頂端是否為對應的左括號；
//        相符則彈出，否則無效。掃完後堆疊為空才有效。
// Algorithm: use a stack. Push openers; for each closer check the top is its matching
//            opener — pop if so, else invalid. Valid only if the stack is empty at the end.

#include <stdbool.h>   // 提供 bool / true / false 型別 / provides the bool, true, false types
#include <stdlib.h>    // 提供 malloc 與 free / provides malloc and free
#include <string.h>    // 提供 strlen / provides strlen

bool isValid(char* s) {
    int n = strlen(s);                  // 字串長度 / length of the string

    // 堆疊最多裝 n 個左括號，所以配置 n 個 char 的空間。
    // The stack holds at most n openers, so allocate space for n chars.
    // malloc 向系統要一塊記憶體，回傳指向它的指標 / malloc requests memory and returns a pointer to it.
    char* stack = (char*)malloc(n * sizeof(char));
    int top = 0;                        // top 是「下一個寫入位置」，也等於目前堆疊大小 / top = next write slot = current stack size

    for (int i = 0; i < n; i++) {       // 從左到右掃描每個字元 / scan every character left to right
        char c = s[i];                  // 取出目前字元（s[i] 是陣列索引）/ current char (s[i] is array indexing)

        if (c == '(' || c == '[' || c == '{') {
            // 是左括號：壓入堆疊。stack[top] = c 寫入，然後 top 往上加一。
            // It's an opener: push it. Write at stack[top], then advance top by one.
            stack[top] = c;
            top++;
        } else {
            // 是右括號。先檢查堆疊是不是空的：top == 0 表示沒有左括號可配對。
            // It's a closer. First check if the stack is empty: top == 0 means no opener to match.
            if (top == 0) {
                free(stack);            // 釋放記憶體，避免洩漏 / free the memory to avoid a leak
                return false;           // 沒有對應的左括號 → 無效 / no matching opener → invalid
            }

            char openTop = stack[top - 1];  // 看堆疊頂端的左括號（不先彈出）/ peek the top opener (top-1 is the last written)

            // 檢查頂端的左括號是否與目前右括號配對；不配對就無效。
            // Check whether the top opener matches the current closer; if not, invalid.
            if ((c == ')' && openTop != '(') ||
                (c == ']' && openTop != '[') ||
                (c == '}' && openTop != '{')) {
                free(stack);            // 同樣要先釋放再回傳 / free before returning
                return false;           // 類型不符 → 無效 / type mismatch → invalid
            }

            top--;                      // 配對成功：彈出頂端（把 top 減一即可）/ matched: pop by decrementing top
        }
    }

    // 掃完所有字元。若堆疊為空 (top == 0)，代表每個左括號都被關閉了 → 有效。
    // All characters scanned. If the stack is empty (top == 0), every opener was closed → valid.
    bool result = (top == 0);
    free(stack);                        // 釋放配置的記憶體 / release the allocated memory
    return result;
}