【栈】括号匹配

Jacob-Chen / 2024-08-23 / 原文

题目描述

给定一个字符串，里边可能包含“()”、“[]”、“{}”三种括号，请编写程序检查该字符串中的括号是否成对出现，且嵌套关系正确。
若括号成对出现且嵌套关系正确，或该字符串中无括号字符，输出：true；
若未正确使用括号字符，输出：false。
实现时，无需考虑非法输入。

用例

输入

(1+2)/(0.5+1)

输出

true

解题思路

创建一个 hashMap 来封装左右括号的映射关系：")" => "("；"]" => "\["；"}" => "{"
遍历字符串，遇到"("，"["，"{" 字符串则入栈；遇到 ")"，"]"，"}" 字符串，则判断栈是否为空，如果为空，或者遇映射关系无法匹配时，则输出 false。

代码实现

public class BracketChecker {
    public static boolean isBalanced(String line) {
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        Stack<Character> stack = new Stack<>();
        for (char c : line.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty() || !map.get(c).equals(stack.peek())) {
                    return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            String line = sc.nextLine();
            System.out.println(isBalanced(line));
        }
    }
}