数据结构【栈】（九）：使用栈检查括号是否匹配

╰+攻爆jí腚メ 2022-02-28 03:30 211阅读 0赞

## 问题描述 ##

给一个字符串表达式，包含一个或多个括号，现要求使用栈检查该字符串表达式中的括号是否平衡。

## 解答思路 ##

遍历字符串中的每个字符，如果：

1）出现左括号则进栈

2）出现右括号则首先检判断栈是否为空，如果不为空，则判断与栈顶元素是否与之匹配，如果匹配则弹出栈顶元素。

3）最后若栈空，则表明匹配成功；否则表明不匹配。

## 代码实现 ##

/**
         * @param s 字符串表达式
         * @return 如果匹配返回，true
         */
        private static boolean isBalanced1(String s) {
            Stack<Character> bracketsStack = new Stack<>();
            char[] text = s.toCharArray();
            for (char x : text) {
                switch (x) {
                    case '{':
                    case '<':
                    case '(':
                    case '[':
                        bracketsStack.push(x);
                        break;
                    case '}':
                        if (bracketsStack.peek() == '{') {
                            bracketsStack.pop();
                            break;
                        } else {
                            return false;
                        }
                    case '>':
                        if (bracketsStack.peek() == '<') {
                            bracketsStack.pop();
                            break;
                        } else {
                            return false;
                        }
                    case ')':
                        if (bracketsStack.peek() == '(') {
                            bracketsStack.pop();
                            break;
                        } else {
                            return false;
                        }
                    case ']':
                        if (bracketsStack.peek() == '[') {
                            bracketsStack.pop();
                            break;
                        } else {
                            return false;
                        }
                    default:
                        break;
                }
            }
            return bracketsStack.empty();
        }
        
        public static void main(String args[]) {
            String s = "({[9*9]})";
            if (isBalanced1(s)) {
                System.out.println(s + " 表达式括号平衡");
            } else {
                System.out.println(s + " 表达式括号不平衡");
            }
        }
    输出：
        ({[9*9]}) 表达式括号平衡

## 代码优化 ##

//括号映射集合
        private final static HashMap<Character, Character> BRACKET_MAP = Maps.newHashMap();
        //括号左符号集合
        private final static Set<Character> BRACKET_KEY_SET = Sets.newHashSet();
    
        //初始化集合
        static {
            BRACKET_MAP.put('[', ']');
            BRACKET_MAP.put('{', '}');
            BRACKET_MAP.put('(', ')');
            BRACKET_MAP.put('<', '>');
            BRACKET_KEY_SET.addAll(BRACKET_MAP.keySet());
        }
    
        /**
         * 判断字符串中的括号是否平衡
         *
         * @param str 字符串
         * @return boolean
         * @author lkf
         * @date 2019/3/20 10:00
         */
        private static boolean isBalanced2(String str) {
            Stack<Character> stack = new Stack<>();
            char[] chars = str.toCharArray();
            for (char c : chars) {
                if (BRACKET_KEY_SET.contains(c)) {
                    stack.push(c);
                }
                if (!stack.isEmpty() && BRACKET_MAP.get(stack.peek()) == c) {
                    stack.pop();
                }
            }
            return stack.isEmpty();
        }
    
        public static void main(String args[]) {
            String s = "({[9*9]})";
            if (isBalanced2(s)) {
                System.out.println(s + " 表达式括号平衡");
            } else {
                System.out.println(s + " 表达式括号不平衡");
            }
        }