题解 | #括号序列#
括号序列
http://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
描述
给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
思路
遍历字符串，若检测到（ { 【则入栈，若检测到）}】则与栈顶元素比较，栈顶元素不是与其匹配的括号，直接返回false，若栈顶元素与其匹配则将栈顶元素出栈继续遍历字符串。
当字符串遍历结束后，若栈内还剩余元素（任何形式的左括号），则返回false，栈为空则证明所有括号正好匹配，返回true。
代码如下
class Solution {
public:
bool isValid(string s) {
stack<int> S;
bool flag=true;
int i=0;
while(i<s.size()&&flag)
{
switch(s[i])
{
case '(':S.push(s[i++]);break;
case '{':S.push(s[i++]);break;
case '[':S.push(s[i++]);break;
case ')':if(!S.empty()&&S.top()=='(') {S.pop();i++;}
else flag=false; break;
case '}':if(!S.empty()&&S.top()=='{') {S.pop();i++;}
else flag=false; break;
case ']':if(!S.empty()&&S.top()=='[') {S.pop();i++;}
else flag=false; break;
default:i++;
}
}
if(S.empty()&&flag) return true;
return false;
}
};
查看20道真题和解析
