题目来源
题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
题目限制
要求最优解
不能暴力
思路分析
这题可以用栈这种数据结构来解决，以下是思路提示：
首先，遍历给定的字符串。
当遇到左括号（也就是 '('、'{'、'[' 这几种）的时候，把它们依次压入栈中。因为后续要靠它们来匹配对应的右括号嘛。
而一旦遇到右括号（')'、'}'、'[' ）时，就去检查栈顶元素。如果栈为空，那说明没有可以匹配的左括号了，直接返回 false ；要是栈不为空，就看看栈顶的左括号和当前遇到的右括号是不是同一类型的（比如栈顶是 '('，当前是 ')' ，这就是同一类型能匹配上的情况），如果是同一类型，那就把栈顶元素弹出，表示这个括号对匹配上了；要是类型不同，那就不符合要求，直接返回 false 。
最后，当整个字符串都遍历完了，如果栈为空，那就说明所有括号都匹配上了，字符串是有效的，返回 true，要是栈里还有元素，那就意味着有左括号没匹配到右括号，返回 false 。
利用栈来处理的好处在于它能很好地按照顺序来记录和匹配括号，符合括号匹配的先后顺序规则，时间复杂度相对比较优哦。大家可以顺着这个思路再详细去思考具体的实现啦。
具体代码
class Solution {
public:
bool isValid(string s) {
stack <char> a;
for(auto i:s)
{
if(i=='('||i=='{'||i=='[')a.push(i);
else
{
if(a.empty())return false;
else
{
char top=a.top();
if((top=='('&&i==')')||(top=='{'&&i=='}')||(top=='['&&i==']'))a.pop();
else{return false;}
}
}
}return a.empty();
}
};在上述代码中，我们使用了std::stack（栈）这个容器来辅助我们解决问题。首先，我们遍历输入的字符串 s。当遇到左括号（'('、'{'、'['）时，我们将其压入栈 a 中。而当遇到右括号时，我们首先检查栈是否为空，如果为空，那就意味着没有对应的左括号来匹配这个右括号，所以直接返回 false。如果栈不为空，我们获取栈顶元素 top，然后检查栈顶的左括号和当前的右括号是否是匹配的类型（例如 '(' 和 ')' 匹配、'[' 和 ']' 匹配、'{' 和 '}' 匹配），如果是匹配的，我们就将栈顶元素弹出，表示这一对括号已经成功匹配；如果不匹配，那么就说明字符串中的括号不是有效的，直接返回 false。当整个字符串都遍历完后，如果栈为空，那就说明所有的括号都找到了对应的匹配括号，字符串是有效的，返回 true；否则返回 false。
这种利用栈来解决括号匹配问题的方法，充分利用了栈的后进先出（LIFO）特性，能够高效且准确地判断字符串中括号的有效性。通过这个问题，我们不仅加深了对栈数据结构的理解，也提升了我们解决实际编程问题的能力。
注意事项
解题思路在编程学习中占据着举足轻重的地位。就拿本题来说，关键在于确定运用何种算法予以攻克。多数人起初往往只会盲目地尝试各种括号匹配方式，然而这毫无成效。若无法洞悉解题的核心思路，个人的编程能力将永远停滞不前。刷题的意义绝非仅仅局限于用代码实现某个题目，更为关键的是要深刻领悟其背后的解题思路，而这其中的核心要素便是算法。它宛如一盏明灯，能够穿透问题的重重迷雾，引导我们找到高效且准确的解决方案，从而在编程的学习之路上实现真正的成长与突破。
标签：面试题,匹配,字节,top,栈顶,括号,字符串,false From： https://blog.csdn.net/ajsjnnn/article/details/144478037