首页  

栈应用之括号匹配     所属分类 DS 浏览量 92
brackets  () {} []
扫描字符串
左括号入栈 push
遇到右括号,左括号出栈 pop ,验证是否匹配 
扫描完毕 查看栈是否为空,为空则全部匹配成功,否则返回false ​​​​


import java.util.Deque; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Set; public class BracketsMatch { private static final Map<Character, Character> map = new HashMap<>(); private static final Set<Character> leftBrackets = new HashSet<>(); private static final Set<Character> rightBrackets = new HashSet<>(); static { map.put(')', '('); map.put(']', '['); map.put('}', '{'); rightBrackets.addAll(map.keySet()); leftBrackets.addAll(map.values()); } private static boolean isValid(String str) { if (str == null || str.isEmpty()) { return false; } int length = str.length(); if (length % 2 != 0) { return false; } Deque<Character> stack = new LinkedList<>(); for (int i = 0; i < length; i++) { char ch = str.charAt(i); // 非法字符 if (!leftBrackets.contains(ch) && !rightBrackets.contains(ch)) { return false; } // 左括号入栈 if (leftBrackets.contains(ch)) { stack.push(ch); continue; } // 栈为空 不匹配 if (stack.isEmpty()) { return false; } // 括号不匹配 if (!stack.pop().equals(map.get(ch))) { return false; } } // 非空 匹配失败 if (!stack.isEmpty()) { return false; } return true; } public static void main(String[] args) { System.out.println(isValid(null)); System.out.println(isValid("")); System.out.println(isValid(" ")); System.out.println(isValid("(")); System.out.println(isValid("[")); System.out.println(isValid("{")); System.out.println(isValid("(]")); System.out.println(isValid("(}")); System.out.println(isValid("{[(())]")); System.out.println(isValid("{[(())")); System.out.println(); System.out.println(isValid("()")); System.out.println(isValid("[]")); System.out.println(isValid("{}")); System.out.println(isValid("(())")); System.out.println(isValid("{(())}")); System.out.println(isValid("{[(())]}")); } } 完整代码 https://gitee.com/dyyx/hellocode/blob/master/web/tech/DS/dsjava/src/main/java/dyyx/BracketsMatch.java

上一篇     下一篇
AVL树与红黑树(RBTree)

aerospike lua udf 例子

计算机专业考研信息

栈应用之表达式求值

数据结构词汇

数据结构三要素