【栈】有效的括号

题目

20. 有效的括号

---

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

解题

方法一：栈模拟

思路

遍历字符串：

• 遇到左括号就把同类型的右括号入栈。
• 遇到右括号时，如果栈为空或者该括号与栈顶元素不同，那么该括号一定没有匹配项，返回 false。

遍历完成后如果栈不为空就说明有没匹配上的左括号，返回 false，否则所有括号都是有效的，返回 true。

代码

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char ch : s.toCharArray()) {
            switch (ch) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                default:
                    if (stack.isEmpty() || ch != stack.pop()) return false;
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
public:
    bool isValid(string s) {
        if (s.length() & 1) return false;
        stack<char> stk;
        for (char& ch : s) {
            switch (ch) {
                case '(':
                    stk.push(')');
                    break;
                case '[':
                    stk.push(']');
                    break;
                case '{':
                    stk.push('}');
                    break;
                default:
                    if (stk.empty() || ch != stk.top()) return false;
                    else stk.pop();
            }
        }
        return stk.empty();
    }
};