[Lc]20有效的括号

题目

题解

• 时间复杂度$O(N)$
• 空间复杂度$O(N)$

class Solution {
public:
    bool isValid(string s) {//用栈
//不能挨个比较，因为有可能两个括号是交错的，用栈最合适
        stack<char> parentheses;//定义栈存左括号
        for(int i=0; i<s.size(); i++){
            if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
                parentheses.push(s[i]);//若左括号出现，压入栈中
            } else{
                if(parentheses.empty()) return false;//若未遍历完栈就清零，说明有右括号无对应的左括号，返回false
                if(s[i] == ')' && parentheses.top() != '(') return false;
                if(s[i] == ']' && parentheses.top() != '[') return false;
                if(s[i] == '}' && parentheses.top() != '{') return false;
                //出现左右括号不对应的情况，返回false
                parentheses.pop();//其他情况说明有对应，栈顶出栈
            }
        }
        return parentheses.empty();//若栈空了说明所有括号均对应完成，返回true；否则返回false
    }
};