20-有效括号

LeetCode 20. Valid Parentheses

LeetCode-20

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Example 1:

Input: s = "()[]{}"
Output: true

Example 2:

Input: s = "(]"
Output: false

method: 栈

用栈存储左边的括号，看右边的括号能不能跟左边的对上，能对上就pop()
最后返回st.empty()是因为

• 如果栈是空的，说明前面都对上了，返回true
• 如果栈非空，说明有左边的括号没能对上右边括号留了下来，返回false

三种情况只要有一种没对上就返回false
最后看栈是不是空的，栈非空说明有没对上的，栈空才是都对上了

bool isValid(string str) {
    stack<char> st;
    for (auto s : str) {
        if (s == '(' || s =='[' || s == '{') st.push(s);
        else {
            if (st.empty()) return false;  // 出现右括号，但栈空，直接返回
            bool b1 = (s == ')' && st.top() != '(');    // 列出不行的情况
            bool b2 = (s == ']' && st.top() != '[');
            bool b3 = (s == '}' && st.top() != '{');
            if (b1 || b2 || b3) return false;   // 只要出现一种不行，就直接返回
            else st.pop();
        }
    }
    return st.empty();
}