题目

思路

括号的匹配，这是一道经典的栈的应用问题。

给我们一个字符串，当我们遍历到左括号时，让其入栈。当我们遍历到右括号时，让栈顶元素出栈，看看栈顶的元素是否和遍历到的右括号匹配。不匹配的话直接false,匹配的话继续遍历，直到栈中所有左括号都出栈，都没有问题，就说明匹配上了。

举例：”[{}]“

所有左括号入栈

遍历到"}"时，弹出栈顶元素，进行比较，相等则说明这一对括号匹配上了。继续进行下一轮的遍历。

然后有三种出现错误的情况：

1.右括号多了： {[]}] (此时对应着栈空了，但是遍历还没有结束)

2.左括号多了： {{[]} (此时对应着遍历字符串结束了，但是栈还是没空)

3.左右括号不匹配：{] (此时对应着遍历到的字符和栈顶元素不相等)

代码细节

1.我们用Deque（双向队列）实现栈，而不用Stack类。因为这个Stackl类已经过时了。

2.左括号入栈的时候，为了方便右括号的比较，就直接将左括号转成对应的右括号入栈了。

基础知识

Deque当栈用的时候的方法。

deque.push() 底层就是 deque.addFirst

deque.pop() 底层就是 deque.removeFirst

代码

import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (ch == '(') {
                deque.push(')');
            } else if (ch == '[') {
                deque.push(']');
            } else if (ch == '{') {
                deque.push('}');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                //deque.isEmpty()对应着右端不匹配的情况
                return false;
            } else {
                //匹配上了，就pop
                deque.pop();
            }
        }
        //如果栈中还有元素，那么说明多出符号来了，还是false
        return deque.isEmpty();
    }
}
//leetcode submit region end(Prohibit modification and deletion)