在「Valid Parentheses」這道題目中，我們需要判斷一個只包含括號的字串是否有效。有效的括號字串需要符合以下條件：

1. 每個左括號 (、[、{ 必須有對應的右括號 )、]、}。
2. 括號必須以正確的順序閉合。

這道題主要考驗的是如何檢查括號的對應和巢狀順序，當遇到這種問題時，堆疊（stack）是一個非常合適的工具。因為堆疊的「後進先出」特性，能夠很好地幫助我們解決括號的巢狀問題。

解法思路

1. 遍歷字串：從左到右逐個檢查字串中的每個字元。
2. 左括號入堆疊：當遇到左括號 (、[、{ 時，將其對應的右括號 )、]、} 推入堆疊。這樣，當我們遇到一個右括號時，可以直接檢查堆疊頂部是否是它的對應括號。
3. 右括號對應檢查：當遇到右括號時，檢查堆疊頂部是否是對應的左括號，如果是，則將其彈出。如果不對應或堆疊為空，則字串無效。
4. 檢查堆疊：最後，堆疊應該是空的，這表明所有括號都正確對應。如果堆疊不為空，則表明有未對應的左括號。

實作：

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ')' && !stk.empty() && stk.top() == '(') {
                stk.pop();
            } else if (s[i] == '}' && !stk.empty() && stk.top() == '{') {
                stk.pop();
            } else if (s[i] == ']' && !stk.empty() && stk.top() == '[') {
                stk.pop();
            } else {
                stk.push(s[i]);
            }
        }

        return stk.empty();
    }
};

左括號 & 右括號 的對應可以用 hash table 來輔助，這樣可以少很多條件式，條件式寫起來比較漂亮。修改後如下，

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        unordered_map<char, char> map = {
            { ')', '(' },
            { '}', '{' },
            { ']', '[' }
        };
        for (int i = 0; i < s.size(); i++) {
            //if (map.find(s[i]) == map.end()) {
            if (!map.count(s[i])) {
                // 左括號 push stack
                stk.push(s[i]);
            } else { // 右括號
                if (stk.empty())
                    return false;

                if (stk.top() != map[s[i]])
                    return false;
                
                stk.pop();
            }
        }
        return stk.empty();
    }
};

參考：
#20. Valid Parentheses