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

Question

事情是这样的：

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

规则：

每个左括号都有对应的右括号。
如果它们之间没有任何类型的开括号，则 2 个括号形成一对。
一对的右括号必须与左括号相同，例如() 有效，但 [) 无效。

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

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

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

这是我的解决方案：

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?的算法完成，如下：

维护一堆字符。
每当您发现左大括号“(”、“{”或“[”时，将其推到堆叠.
每当您找到右大括号 ')', '}' OR ']' 时，检查顶部是否 stack是对应的左括号，如果是，则出栈，否则打破循环和 return false.
重复步骤 2 - 3 直到字符串结束。

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

Answer 1

这是一个非常清晰的算法，看来你是对的。那么为了改变访问字符的方式，为什么不使用String#charAt方法呢？

您可能还想将方法的 return 类型从字符串 "YES" 或 "NO" 更改为 true 或 false 类型 boolean:

static boolean isValidBracketString(String string) {
    Stack<Character> stack = new Stack<>();
    for(int i=0; i< string.length(); i++){
        if(string.charAt(i) == '{' || string.charAt(i) == '[' || string.charAt(i) == '('){
            stack.push(string.charAt(i));
        } else if(string.charAt(i) == '}' || string.charAt(i) == '}' || string.charAt(i) == ')') {
            if(stack.size() == 0)
                return false;
            switch(stack.pop()){
                case '(':
                    if(string.charAt(i) != ')')
                        return false;
                    break;
                case '[':
                    if(string.charAt(i) != ']')
                        return false;
                    break;
                case '{':
                    if(string.charAt(i) != '}')
                        return false;
                    break;
            }
        }
    }
    return stack.size() == 0;
}

Answer 2

您可以将字符串转换为 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;
}

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

finding validity of bracket string in java

java

regex

string

validation

brackets