栈----1.有效的括号

20. 有效的括号 - 力扣（LeetCode）

/**

        括号特性:

                左括号必定先出现,每个左括号都需要一个右括号与之匹配,后出现的左括号先匹配

        解法:

                依据后出现的左括号先匹配,很容易联想到栈,即后进先出

                遍历字符串,遇到左括号就在栈中添加一个对应的右括号

                遇到右括号就弹出栈顶元素判断是否一致(当前遍历到的最后一个出现的左括号是否能闭合)

            不合法:    

                若弹出的右括号与遇到的右括号不一致---> 左右类型不匹配,不合法

                若遇到右括号时栈中无元素可弹出---> 右括号多余无法闭合,不合法

                若字符串遍历结束栈中仍有元素---> 左括号多余无法闭合,不合法

*/

class Solution {/**括号特性:左括号必定先出现,每个左括号都需要一个右括号与之匹配,后出现的左括号先匹配解法:依据后出现的左括号先匹配,很容易联想到栈,即后进先出遍历字符串,遇到左括号就在栈中添加一个对应的右括号遇到右括号就弹出栈顶元素判断是否一致(当前遍历到的最后一个出现的左括号是否能闭合)不合法:    若弹出的右括号与遇到的右括号不一致---> 左右类型不匹配,不合法若遇到右括号时栈中无元素可弹出---> 右括号多余无法闭合,不合法若字符串遍历结束栈中仍有元素---> 左括号多余无法闭合,不合法*/public boolean isValid(String s) {//利用双端队列模拟栈Deque<Character> stack = new ArrayDeque<>();//按规则遍历字符串for(char c : s.toCharArray()) {//将对应的右括号入栈if(c == '(') {stack.push(')');} else if(c == '[') {stack.push(']');} else if(c == '{') {stack.push('}');}//遇到右括号,判断是否合法else {//右括号多余或左右类型不匹配 不合法if(stack.isEmpty() || stack.pop() != c) {return false;}}}//左括号多余if(!stack.isEmpty()) {return false;}return true;}
}