题解 | #有效括号序列#
有效括号序列
https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2
2022.0902算法第52题有效括号序列
这道题我自己是想不出来，刚开始看答案都没看明白
有map的那个还没看明白呢
不过使用栈进行求解的方法倒是明白了，这个算是利用括号匹配的特性了
想不出来
主要思路就是：
遇到左符号时，将左符号加入到栈中
遇到右符号时，看此时的右符号是否与栈顶元素组成对应的符号，不能则不是有效的序列
这里注意，栈如果为空也不是有效序列
最终遍历结束后，如果栈非空，则不是有效序列
以上思路比较简单，具体实现时，细节问题就是需要好多判断，而且时嵌套的判断
很容易出错
因此，当遇到左符号时，将相应的右符号加入栈中，
这样后面判断时只需要判断是否相等就行。
bool isValid(string s) {
//利用栈存储左侧的符号，这里为了好比较存储的是左符号对应的右括号
stack<char> s1;
//对字符串进行遍历
for(int i=0;i<s.size();i++){
//遇到左符号，向栈中添加入相应的右括号
if(s[i]=='(') s1.push(')');
else if (s[i]=='{') s1.push('}');
else if (s[i]=='[') s1.push(']');
//当遇到右括号时，与栈顶元素进行比较，如果不等，则返回false
else if (s1.empty()||s[i]!=s1.top()) return false;
//如果相等，则将栈顶元素取出
else s1.pop();
}
//判断栈中是否还剩余元素，有的话，返回false
if(!s1.empty())
return false;
return true;
}
查看15道真题和解析