代码随想录-栈与队列-有效的括号（括号匹配）

neromegumi / 2024-12-21 / 原文

题目

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

题解

经典题目，用栈解决。但也有新的收获。
一般思路：左括号入栈，右括号判断栈顶是否匹配，匹配则栈顶出栈，最后判断栈是否为空
优化思路：如果字符是左括号则让右括号入栈，是右括号则判断与栈顶是否相同（通过这一步可以简化代码），不匹配则返回false，匹配则栈顶出栈。最后判断栈是否为空

代码

class Solution {
public:
    stack<char> st;
    bool isValid(string s) {
        if(s.size() % 2 != 0) return false;//如果字符串长度奇数一定不匹配
        for(auto &c : s){
            if (c == '(') st.push(')');
            else if (c == '{') st.push('}');
            else if (c == '[') st.push(']');
            //第一种情况：左括号则对应的右括号入栈
            else if( st.empty() || c != st.top())return false;
            //第二种情况：栈空 或 右括号和栈顶不匹配
            else st.pop();
            //第三种情况：括号匹配则栈顶出栈
        }
        if(st.empty())return true;
        else return false;
    }
};