Java括号匹配算法求解（用栈实现）

什么是括号匹配？

在计算机科学中，括号匹配是指验证一个表达式中的括号是否是成对出现、嵌套正确的。例如：()[]{}{}是一个合法的括号序列，而([)]则是不合法的括号序列。

如何检查括号匹配？

使用栈数据结构可以很容易地完成括号匹配的检查。 遍历字符串中的每个字符，如果遇到左括号则入栈，如果遇到右括号则出栈，出栈的同时判断是否与当前右括号匹配。如果栈为空，说明左右括号不匹配，如果最后栈不为空，也说明左右括号不匹配，否则左右括号匹配。

Java代码

public static boolean checkBracket(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '(' || ch == '[' || ch == '{') {//左括号入栈
            stack.push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {//右括号出栈，判断和左括号是否匹配
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if (ch == ')' && top != '(') {
                return false;
            }
            if (ch == ']' && top != '[') {
                return false;
            }
            if (ch == '}' && top != '{') {
                return false;
            }
        }
    }
    return stack.isEmpty();//最后判断栈是否为空
}

示例说明

下面给出两个示例说明。

示例1

输入：()[{}][]

输出：true

解释：左右括号都匹配，合法括号序列。

示例2

输入：()[]{}}

输出：false

解释：左右括号不匹配，不合法括号序列。