检查 java 中的有效括号

Question

我正在尝试确定给定的输入是否为有效括号。输入字符串由 '(', ')', '{', '}', '[' 和 ']' 组成。
输入字符串在以下情况下有效：

1.Open 括号必须由相同类型的括号闭合。
2.Open 括号必须以正确的顺序闭合。 3.空字符串有效

但是我下面使用递归的代码在有效情况下不起作用。假设转到基本情况（当输入为“”时），而是转到 for 循环之后的 return 语句。

class Solution {

    public boolean validParen(String input) {

        if(input.isEmpty()) {
            return true;
        }

        else {
            for (int i = 0; i < input.length() - 1; i++) {
                if ((input.charAt(i) == '(' && input.charAt(i + 1) == ')') ||
                        (input.charAt(i) == '{' && input.charAt(i + 1) == '}') ||
                        (input.charAt(i) == '[' && input.charAt(i + 1) == ']')) {
                    input = input.substring(0, i) + input.substring(i + 2);
                    System.out.println("Input is " + input);
                    validParen(input);
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        //System.out.println(sol.validParen("")); 
        //System.out.println(sol.validParen("()")); // returns false for some reason 
        //System.out.println(sol.validParen("()[]{}")); // returns false for some reason
        //System.out.println(sol.validParen("(]"));
        //System.out.println(sol.validParen("([)]"));
        //System.out.println(sol.validParen("{[]}")); // returns false for some reason
    }
}

Answer 1

你试过更换

validParen(input);

与

return validParen(input);

？否则这一行并没有真正做太多;）

从调用顺序的角度来看，无论您是从 a() 还是从其他任何地方调用方法 a() 都没有关系。让我们看一个简单的例子

public int getOne() {
   return 1;
}

public int getA(int a) {
   /*
   what you do here is call getOne(). The method will be called,
   and it will produce some result, but this result will not be persisted
   in any way, you will just go to the next line where the original a's
   value will be returned
    */
   getOne(); 
   return a;


}

这个案例是不是更清楚一点了？显然，如果您调用 getA(2)，将返回 2，而不是 1，即使在内部调用 getOne() - 它的结果将被忽略。

Answer 2

如评论所说，可以考虑使用堆栈。当前字符为(或{或[时，将它们入栈。当当前字符为)或}或]时，检查堆栈中是否有对应的字符（对于有效输入，它必须存在）并弹出它。

import java.util.Stack;

class Solution {

    public boolean validParen(String input) {

        if (input.isEmpty()) {
            return true;
        } else {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < input.length(); i++) {
                char current = input.charAt(i);
                if (current == '(' || current == '[' || current == '{') {
                    stack.push(current);
                } else {
                    if(stack.isEmpty()) {
                          return false;
                    }
                    char peekChar = stack.peek();
                    if ((current == ')' && peekChar != '(')
                            || (current == '}' && peekChar != '{')
                            || (current == ']' && peekChar != '[')) {
                        return false;  // for a valid input, a close brackets must have an open brackets
                    } else {
                        stack.pop();
                    }
                }
            }
            return true; 
        }
    }


    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validParen(""));
        System.out.println(sol.validParen("()"));
        System.out.println(sol.validParen("()[]{}"));
        System.out.println(sol.validParen("(]"));
        System.out.println(sol.validParen("([)]"));
        System.out.println(sol.validParen("{[]}"));
    }

}

Answer 3

导入java.util.Stack；

public class ValidBracesTest {

public static void main(String[] args) {

    System.out.println(isValid("( [ { } ] )".toCharArray())); // valid
    System.out.println(isValid("([{}])".toCharArray())); // valid
    System.out.println(isValid("([)]".toCharArray())); // invalid
    System.out.println(isValid("(}".toCharArray())); // invalid

}

public static boolean isValid(char[] charArray) {
    Stack<Character> container = new Stack<Character>();

    for (char c : charArray) {

        if (c == ' ') {
            continue;
        }

        if (c == '(' || c == '{' || c == '[') {
            container.push(c);
        } else if (c == ')' && container.peek() == '(' 
                || (c == '}' && container.peek() == '{')
                || (c == ']' && container.peek() == '[')) {
            container.pop();
        } else {
            return false;
        }

    }

    return container.isEmpty();
}

}

Answer 4

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(int i =0; i < s.length(); i++){
       Character currentChar = s.charAt(i);
       if (currentChar == '(' || currentChar == '{' || currentChar == '[') {
            stack.push(currentChar);
       } else if(!stack.isEmpty()){
           if (currentChar == ')' && stack.peek() == '(' 
            || (currentChar == '}' && stack.peek() == '{')
            || (currentChar == ']' && stack.peek() == '[')) {
                stack.pop();
            } else {
                return false;
            }
       } else {
            return false;
        }
    }

    return stack.isEmpty();
}

Answer 5

这应该是一个优雅的版本，您可以在其中按下括号的反义词并检查完整性。

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (char c : s.toCharArray()) {
        if (c == '(')
            stack.push(')');
        else if (c == '{')
            stack.push('}');
        else if (c == '[')
            stack.push(']');
        else if (stack.isEmpty() || stack.pop() != c)
            return false;
    }
    return stack.isEmpty();
}

检查 java 中的有效括号

Check for Valid Parentheses in java

java

algorithm

math

recursion

parentheses