java - 如何检查 String 是否包含 Java 中的右组括号

Question

如何检查字符串是否正确分组。例如，正确完成以下组:

({})
[[]()]
[{()}]

接下来做错了:

{(})
([]
[])

正确的字符串不能以错误的顺序关闭组，打开组但无法关闭它，或者在打开之前关闭组。

输入字符串可能包含任何符号“()”、“{}”或“[]”以创建组。如果字符串为空或以其他方式正确分组，则输出返回 True，如果分组不正确，则输出返回 False。

谁能给我一些提示。

Answer 1

主要思想是使用Stack 来跟踪预期的下一个对应括号。 以下代码将起作用:

public boolean isValid(String s) {
    HashMap<Character, Character> closeBracketMap = new HashMap<Character, Character>();
    closeBracketMap.put(')', '(');
    closeBracketMap.put(']', '[');
    closeBracketMap.put('}', '{');
    HashSet<Character> openBracketSet = new HashSet<Character>(
        closeBracketMap.values());
    Stack<Character> stack = new Stack<Character>();

    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char cur = chars[i];
        if (openBracketSet.contains(cur)) {
            stack.push(cur);
        } else { // close brackets
            if (stack.isEmpty()) {
                return false;
            }
            if (closeBracketMap.get(cur) != stack.peek()) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.isEmpty();
}