【栈和队列OJ】一、有效的括号
文章目录
- 题目链接
- 思路
- 代码实现
题目链接
Leetcode链接：20. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
- 1 <= s.length <= 104
- s 仅由括号 ‘()[]{}’ 组成
思路
- 遍历字符串，若为左括号，入栈
- 若为右括号，首先判断栈是否为空，为空直接返回
false，若不为空，取栈顶元素，若栈顶元素是与之对应的左括号则出栈，否则返回false - 最后遍历完字符串之后，判断栈是否为空，为空返回
true，否则返回false
代码实现
class Solution {
public:
bool isValid(string s) {
stack<char> mystack;
//遍历字符串
for(int i = 0; i < s.size(); ++i)
{
//为左括号入栈
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
{
mystack.push(s[i]);
}
else
{
//遍历到右括号，如果栈为空，则不匹配
if(mystack.empty())
return false;
//不为空
char top = mystack.top();
mystack.pop();
if(s[i] == ')' && top != '('
|| s[i] == '}' && top != '{'
|| s[i] == ']' && top != '[')
{
return false;
}
}
}
//最后判断栈是否为空，如果栈为空，则证明这是一个有效的字符串
return mystack.empty();
}
};