您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

有效的括号(图文)

第十三双眼睛2023-11-22【数据结构与算法】人已围观

简介有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路：用两个栈，先将字符串压入第一个栈中，然后开始循环，先从第一个栈中弹出一个元素，再查看第一个栈中的下一个元素，和第二个栈中的一个元素，按照如下规则：
如果当前符号和栈一中的符号配对，则栈一中的元素出栈，如果不匹配，就和栈二中的符号比较，如果匹配，则栈二中的元素出栈，如果都不匹配，则压入栈二中，如此往复，当栈一中的元素空的时候，结束循环，这个时候查看栈二中的元素是否为空，如果此字符串合法，则能全部清空两个栈，如果不匹配，则第二个栈中不会为空。代码如下：

public boolean method1(String s) {
   if (s.length() % 2 != 0) {
       return false;
   }
   LinkedList<Character> stack1 = new LinkedList();
   LinkedList<Character> stack2 = new LinkedList();
   for (int i = 0; i< s.length(); i++) {
       stack1.addLast(s.charAt(i));
   }
   while (stack1.size() > 0) {
       Character currentChar = stack1.removeLast();
       Character preChar = stack1.peekLast();
       Character nextChar = stack2.peekLast();
       //如果和前面得匹配，则两个都消除
       if (isPair(preChar, currentChar)) {
           stack1.removeLast();
       } else if (isPair(currentChar, nextChar)) {
           //如果和后面得匹配，则两个也都消掉
           stack2.removeLast();
       } else {
           //如果和前后得都不匹配,则入到后面得栈
           stack2.addLast(currentChar);
       }
   }
   if (stack2.size() == 0) {
       return true;
   }
   return false;
}

public boolean isPair(Character c1, Character c2) {
   if (c1 == null || c2 == null) {
       return false;
   }
   if (c1 =='{' && c2 == '}') {
       return true;
   }
   if (c1 =='[' && c2 == ']') {
       return true;
   }
   if (c1 =='(' && c2 == ')') {
       return true;
   }
   return false;
}

Tags：

很赞哦！ ()

上一篇：最长公共前缀

下一篇：合并两个有序链表(图文)