20. 有效的括号
20. 有效的括号
分析
由于栈结构的特殊性，非常适合做对称匹配类的题目。即必须按照出现的顺序反向出现另一半的这种题目
括号匹配就是一个典型的题目，实际上编译器词法分析的过程中就是用栈来判断多层嵌套的括号是否完整的。除此之外，Linux 系统中，cd 这个进入目录的命令我们应该再熟悉不过了。
cd a/b/c/../../
这个命令最后进入 a 目录，系统是如何知道进入了 a 目录呢 ，这也是栈的应用（其实可以出一道相应的面试题了）（还真有 71. 简化路径）
说会本题的解题思路：
我最开始想到用三个栈，每一个栈处理一种括号，但是这样的话， ([)] 的结果就会是 true，但是我们知道这样是不对的。所以最总还是只能用一个栈来处理。
然后实际的处理逻辑是，遍历字符串的所有字符
- 碰到左括号，直接入栈，
- 喷到右括号，看栈顶是不是与之对应的左括号，是则出栈，否则直接返回 false
这么做法是没问题的，不过还有一个更方便简洁的做法，就是遍历字符的时候 - 碰到左括号，把与之对应的右括号入库
- 碰到右括号，直接对比栈顶是不是与之相同的字符，是则出栈，否则直接报错
其实无论是什么做法，都免不了从左括号到右括号，或者右括号到左括号的映射。但是第二种代码写起来更简洁，更简短，更好理解。
这时，我们也能总结出栈这个数据结构的最佳使用姿势：如果待入栈的元素跟栈顶的元素相同，则弹出栈顶元素，同时处理下一个待入栈的元素。
解题
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if ('(' == chars[i]) {
stack.push(')');
}else if ('[' == chars[i]) {
stack.push(']');
}else if ('{' == chars[i]) {
stack.push('}');
}else{
if(stack.peek() == null){
return false;
}else if(stack.peek() != chars[i]){
return false;
}else{
stack.pop();
}
}
}
return stack.size() == 0 ;
}