java - 在java中检查有效的括号

Question

我试图查明给定的输入是否是有效的括号。输入字符串由 '(', ')', '{', '}', '[' 和 ']' 组成。
如果满足以下条件，则输入字符串有效:

1.左括号必须由相同类型的括号闭合。
2.左括号必须以正确的顺序闭合。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

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

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("{[]}"));
    }

}