栈和队列——有效括号

20. 有效的括号

添加链接描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

思路

编辑器检查括号也是用栈检查的
有三种错误方式

1. 左括号多了
2. 右括号多了
3. 左右括号对不上

代码

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2) return false;
        stack<char> st;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(') st.push(')');
            else if(s[i]=='[') st.push(']');
            else if(s[i]=='{') st.push('}');
            // 右边括号多了|| 左右不等 
            else if(st.empty() || s[i]!=st.top()) return false;
            else  st.pop();
        }
        // 左括号多了，括号没配对完
        if(!st.empty()) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码小细节

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2) return false;
        stack<char> st;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(') st.push(')');
            else if(s[i]=='[') st.push(']');
            else if(s[i]=='{') st.push('}');
            // 右边括号多了|| 左右不等 
            
            
            else if(s[i]!=st.top() || st.empty()) return false;
            // st.empty() || s[i]!=st.top() 交换了顺序，报错
            

            else  st.pop();
        }
        // 左括号多了，括号没配对完
        if(!st.empty()) return false;
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

if中的或判断顺序
if(conditionA || conditionB);
先判断A，A为真就不判断B，输出true，A为假再判断B
代码中，交换顺序错，是因为st.top()，当栈st为空时，以为top()返回NULL，其实top()返回超尾-1，所以使用top()最好先判断empty（），本文中st.empty()有两重意思：为空，右括号多了；不为空，或中第二个开始判断（为第二个top不为空的先决条件）