Проверьте допустимые скобки в Java - PullRequest
Новая
       16

Проверьте допустимые скобки в Java

0 голосов
/ 21 мая 2018

Я пытаюсь выяснить, является ли данный ввод правильными скобками или нет.Входная строка состоит из '(', ')', '{', '}', '[' и ']'.
Входная строка действительна, если:

1.Открытые скобкидолжны быть закрыты скобками того же типа.
2.Открытые скобки должны быть закрыты в правильном порядке.3. пустые строки действительны

Однако мой код ниже с использованием рекурсии не работает в допустимых случаях.Предполагается перейти к базовому случаю (когда input равен ""), но вместо этого переходит к оператору return после цикла for.

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
    }
}

Ответы [ 2 ]

0 голосов
/ 21 мая 2018

Как сказано в комментарии, вы можете рассмотреть возможность использования стека.Когда текущий символ ( или { или [, поместите их в стек.Если текущий символ ) или } или ], проверьте, есть ли аналог в стеке (для правильного ввода он должен существовать), и вытолкните его. 

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

}
0 голосов
/ 21 мая 2018

Вы пытались заменить 

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() вызывается внутренне - его результат игнорируется.

...