【LeetCode Hot 100】20. 有效的括号

题目描述

这个题目在讲解栈的应用的时候是常用的例子，在遍历括号串的时候维护一个栈结构，如果当前字符是前括号，暂时没有与之配对的后括号，则先将其压入栈中。C++ STL和Java都提供了对应的容器，但是由于我们知道栈的大小不可能超过括号串的长度，所以也可以手动用数组模拟，这样运行速度可能快些。

// C++
class Solution {
public:
    bool isValid(string s) {
        if (s.length() % 2)
            return false;
        stack<char> stk;
        for (auto& ch : s) {
            switch (ch) {
            case ')':
                if (stk.empty() || stk.top() != '(')
                    return false;
                stk.pop();
                break;
            case ']':
                if (stk.empty() || stk.top() != '[')
                    return false;
                stk.pop();
                break;
            case '}':
                if (stk.empty() || stk.top() != '{')
                    return false;
                stk.pop();
                break;
            default:
                stk.push(ch);
                break;
            }
        }
        return stk.empty();
    }
};