stack实现括号匹配

stack实现括号匹配

1.通过String类的内置函数置空string

public static boolean isValidByIf(String s){
while (s.contains("{}")||s.contains("[]")||s.contains("()")){
s=s.replace("{}","");
s=s.replace("[]","");
s=s.replace("()","");

    }
    return s.isEmpty();
}

2.通过stack实现

public static boolean isValidByStack(String s) {
       Stack<Character> stack = new Stack<>();
       char[] ch = s.toCharArray();
       for (int i = 0; i < ch.length; i++) {//遍历字符数组，是左括号入栈
           if (ch[i] == '(' || ch[i] == '[' || ch[i] == '{') {
               stack.push(ch[i]);
           } else {
//                右括号
               if (stack.isEmpty()) return false;//stack为空不存在左括号，只有右括号所有无效
//                弹出栈顶元素
               Character left = stack.pop();
               if (left == '(' && ch[i] != ')') return false;
               if (left == '{' && ch[i] != '}') return false;
               if (left == '[' && ch[i] != ']') return false;
           }
       }
//        stack为空，则括号匹配，有效，否则不为空，无效
       return stack.isEmpty();
   }

3.通过hashmap键值对的形式实现

 public static boolean isValidByHM(String s) {
        Stack<Character> stack = new Stack<>();
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {//遍历字符数组，是左括号入栈
            if (hashMap.containsKey(ch[i])) {
                stack.push(ch[i]);
            } else {
//                右括号
                if (stack.isEmpty()) return false;//stack为空不存在左括号，只有右括号所有无效
//                弹出栈顶元素
                Character left = stack.pop();
//                hashMap.get(left)根据栈弹出的left左括号get取值为对应的右括号，而ch[i]为右括号，不等则false
                if (ch[i]!=hashMap.get(left)) return false;
            }
        }
//        stack为空，则括号匹配，有效，否则不为空，无效
        return stack.isEmpty();
    }