【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();
}
};