思路
- 先进的左括号后匹配,后进的左括号先匹配
- 如果栈非空,新元素与栈顶元素匹配(注意哪头是顶),则栈顶元素出栈
- 如果栈空,新元素直接压栈
- 如果2中进的是右括号,无左括号匹配,也直接压栈就行,最后通过empty返回false,详细看代码
代码
class Solution {
public:
bool isValid(string s) {
stack<char> stack;
for(int i=0; i<s.length(); ++i){
char c = s[i];
if(!stack.empty()){
char t = stack.top();
if(t=='(' && c==')'
|| t=='[' && c==']'
|| t=='{' && c=='}'){
stack.pop();
continue;
}
}
stack.push(c);
}
return stack.empty();
}
};