L20 有效的括号
题目链接
https://leetcode.cn/problems/valid-parentheses/
题目描述
给定一个只包括 '('、')'、'{'、'}'、'['、']' 的字符串 s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例
示例 1
输入： s = “()”
输出： true
示例 2
输入： s = “()[]{}”
输出： true
示例 3
输入： s = “(]”
输出： false
示例 4
输入： s = “([])”
输出： true
示例 5
输入： s = “([)]”
输出： false
提示
s仅由括号'()[]{}'组成
题解
这个题中，每个左括号都需要在之后遇到一个同类型的右括号来"抵消"掉，而且括号之间不能交叉（比如 ([)] 就是无效的）。
这种"后出现的左括号，需要先被匹配"的特性，就需要"后进先出"，也就可以用栈来解决：
- 遇到左括号时，入栈，等待后续匹配。
- 遇到右括号时，检查栈顶元素是否是对应的左括号：
- 如果是，匹配成功，栈顶出栈。
- 如果不是，说明括号配对失败，直接返回
false。
- 遍历完所有字符后，如果栈为空，说明所有括号都成功匹配；否则说明有未匹配的左括号。
C++ STL 的 stack 容器提供了栈的核心操作，常见用法如下表：
| 功能 | 示例代码 | 备注 |
|---|---|---|
| 创建 | stack<int> stk; | 创建一个空栈 |
| 入栈 | stk.push(1); | 将元素添加到栈顶 |
| 出栈 | stk.pop(); | 移除栈顶元素，不返回该元素 |
| 访问栈顶 | stk.top() | 返回栈顶元素，不移除 |
| 判空 | stk.empty() | 栈为空返回 true，否则返回 false |
| 元素个数 | stk.size() | 返回队列中元素的数量 |
借助 stack，我们的代码可以这么写：
class Solution
{
public:
bool isValid(string s)
{
int n = s.size(); //获取字符串长度用于遍历
stack <char> bracketStk; //创建括号栈
for(int i = 0;i < n;i++)
{
if(bracketStk.empty()) //栈空
{
bracketStk.push(s[i]);
continue;
}
if(s[i] == '{' || s[i] == '[' || s[i] == '(') //左括号入栈
{
bracketStk.push(s[i]);
continue;
}
else //右括号匹配
{
if(bracketStk.top() == '{' && s[i] == '}')
bracketStk.pop(); //出栈
else if(bracketStk.top() == '[' && s[i] == ']')
bracketStk.pop(); //出栈
else if(bracketStk.top() == '(' && s[i] == ')')
bracketStk.pop(); //出栈
else //配对失败
return false;
}
}
return bracketStk.empty();
}
};代码不难写，会用 stack 就行。我们循环遍历这个字符串，每一轮只解决三个问题：
如果栈空的话，就把当前元素入栈，然后继续下一轮。（其实这里可以直接再加一步：如果栈空并且当前括号是右括号，可以直接返回 false，不过不加也不影响，代码更简洁）
如果是左括号的话，直接入栈。
如果是右括号的话，进行匹配，如果失败，就直接返回 false。
这道题我也借助 AI 补充了力扣提交代码之外的本地测试部分，可以直接在自己的编译器中输入数据并运行。完整代码已经整理到 GitHub：https://github.com/C571467648/blog。其他题目也是采用相同的方式整理，建议有需要的话一次性下载使用。如果觉得比较麻烦，或者只想研究题目本身，也可以直接在力扣平台研究 class Solution 部分的代码。
本题讲解就到这里啦，欢迎交流讨论~
本文内容主要来自个人学习与实践总结，受限于个人技术水平，难免存在理解不准确或表述疏漏等错误。 若您发现问题，或愿意就相关内容进一步交流，欢迎通过邮箱 571467648@qq.com 与我联系。感谢您的阅读与指正。