06.判断括号是否匹配

目录介绍

• 01.问题描述
• 02.问题解答
• 03.算法思路
• 04.代码展示

01.问题描述

• 利用栈实现判断字符串中的括号是否都是配对的

02.问题解答

• 注意：“{[()]}”类似的可以匹配，“{(}}”类似的无法匹配。

03.算法思路

• 通过判断左括号和右括号的数量是否相等，无法排除不同类括号交叉出现的情况。比如([)]不能算匹配。
• 需要考虑字符串中包含非括号的字符
• 嵌套情况下的匹配，比如这种{<>},嵌套的最里层一定是相邻匹配的。
• 遇到左括号入栈，遇到右括号则判断是否跟栈顶的左括号匹配，如果不匹配，则出现了交叉，整个字串括号不匹配。如果匹配，则栈顶括号出栈。循环该过程，最终栈为空则匹配。

04.代码展示

• 代码如下所示
  • 需要注意的是在循环结束后，判断栈是否为空，如果不为空，同样是无法匹配。

  public static boolean isComplete(String s){
      Stack<String> left=new Stack<String>();
      while (!s.isEmpty()){
          //取字符串首字母
          String character=s.substring(0,1);
          //剩余的字符串
          s=s.substring(1);
          if(character.equals("{")||character.equals("[")||character.equals("(")){
              //如果是左括号，则压入栈
              left.push(character);
          }else if(character.equals(")")||character.equals("]")||character.equals("}")){
              //首先检查栈是否为空
              if(left.isEmpty())
                  return false;
              //弹出最后的左括号
              String leftChar=left.pop();
              //检查左右括号是否匹配
              if(character.equals(")")){
                  if(!leftChar.equals("("))
                      return false;
              }else if(character.equals("]")){
                  if(!leftChar.equals("["))
                      return false;
              }else if(character.equals("}")){
                  if(!leftChar.equals("{"))
                      return false;
              }
          }
      }
      //此时栈中不应该再有左括号
      return left.isEmpty();
  }