java - 在java中查找括号字符串的有效性

Question

事情是这样的:

给定一个字符串，其元素是括号( ) [ ] { }。

规则:

1. 每个左括号都有一个相应的右括号。

2. 如果两个括号之间没有任何类型的开括号，则它们构成一对。

3. 一对的右括号必须与左括号相同，例如() 有效，但 [) 无效。

任务是根据这些标准确定括号字符串是否有效。

有效字符串示例:{}[]()

示例无效字符串:{[}]

这是我的解决方案:

static String braces(String string) {
   Stack<String> stack = new Stack<>();
   for(int i = 0; i <= string.length() - 1; i ++){

       if(string.substring(i, i+1).equals("("))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals("["))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals("{"))
           stack.push((string.substring(i, i+1)));

       else if(string.substring(i, i+1).equals(")"))
           if(stack.peek().equals("("))
               stack.pop();
           else
               return "NO";

       else if(string.substring(i, i+1).equals("]"))
           if(stack.peek().equals("["))
               stack.pop();
           else
               return "NO";

       else if(string.substring(i, i+1).equals("}"))
           if(stack.peek().equals("{"))
               stack.pop();
           else 
               return "NO";
       }
   return "YES";
   }

这是根据这里的算法完成的How to find validity of a string of parentheses, curly brackets and square brackets?如下:

1. 维护一堆字符。
2. 每当你发现左大括号“(”、“{”或“[”时，将其推到 堆栈。
3. 每当您发现右大括号 ')'、'}' 或 ']' 时，请检查顶部是否 stack是对应的左括号，如果是，则出栈， 否则打破循环并返回 false。
4. 重复步骤 2 - 3，直到字符串末尾。

但我不喜欢它的样子。访问 String 元素的方式有点笨拙，我很好奇是否有另一种更清晰的方法来解决问题，也许使用正则表达式？

Answer 1

您可以将字符串转换为 char[] 并对其进行迭代。此外，您可以通过使用右括号到左括号的 Map 使代码看起来更优雅:

// Initialize some helper structures:
private static Map<Character, Character> CLOSE_TO_OPEN;
private static Set<Character> OPENERS;
static {
    CLOSE_TO_OPEN = new HashMap<>();
    CLOSE_TO_OPEN.put(')', '(');
    CLOSE_TO_OPEN.put(']', '[');
    CLOSE_TO_OPEN.put('}', '{');
    OPENERS = new HashSet<>(closeToOpen.values());
}

public static boolean braces (String str) {
    Stack<Character> stack = new Stack<>();
    for (Character c : str.toCharArray()) {

        // If it's an opening bracket, push it to the stack
        if (OPENERS.contains(c)) {
            stack.push(c);
        } 
        // If it's a closing bracket, check the last opener
        else if (CLOSE_TO_OPEN.containsKey(c)) {
            try {
                Character opener = stack.pop();
                // Handle mismatches brackets
                if (!CLOSE_TO_OPEN.get(c).equals(opener)) {
                    return false;
                }
            } 
            // If the stack is empty, there's a redundant closer
            catch (EmptyStackException ignore) {
                return false;
            }
        }
    }

    // If the stack isn't empty once we're done with the string, 
    // there are redundant openers
    if (!stack.empty) {
        return false
    }
    return true;
}