【栈和队列OJ】一、有效的括号

题目链接

Leetcode链接：20. 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

输入：s = "()[]{}"
输出：true
1
2

示例 3：

输入：s = "(]"
输出：false
1
2

提示：

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

思路

• 遍历字符串，若为左括号，入栈
• 若为右括号，首先判断栈是否为空，为空直接返回false，若不为空，取栈顶元素，若栈顶元素是与之对应的左括号则出栈，否则返回false
• 最后遍历完字符串之后，判断栈是否为空，为空返回true，否则返回false

代码实现

class Solution {
public:
    bool isValid(string s) {
		
        stack<char> mystack;
        //遍历字符串
        for(int i = 0; i < s.size(); ++i)
        {
        	//为左括号入栈
            if(s[i] == '(' || s[i] == '{' || s[i] == '[')
            {
                mystack.push(s[i]);
            }
            else
            {
                //遍历到右括号，如果栈为空，则不匹配
                if(mystack.empty())
                    return false;
                //不为空
                char top = mystack.top();
                mystack.pop();

                if(s[i] == ')' && top != '('
                || s[i] == '}' && top != '{'
                || s[i] == ']' && top != '[')
                {
                    return false;
                }
                
            }
        }
        //最后判断栈是否为空，如果栈为空，则证明这是一个有效的字符串      
        return mystack.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35