Что необходимо изменить в скобочной последовательности [((())()(())]], чтобы она стала правильной?

Question

Что необходимо изменить в данной скобочной последовательности с точки зрения Java, чтобы она стала правильной?

Пробовал всевозможными способами с помощью интерпретатора repl.it проверить верность тех или иных манипуляций с удалением, на мой взгляд, неверных скобок, но каждый раз интерпретатор выдает некорректный вывод по ошибкам, например, как здесь:

Main.java:3: error: illegal start of expression
    System.out.println([((())()(())]); 
                       ^
Main.java:3: error: -> expected
    System.out.println([((())()(())]); 
                            ^
Main.java:3: error: ')' expected
    System.out.println([((())()(())]); 
                             ^
3 errors
exit status 1

Answer 1

В общем, проведя небольшой рессерч, я нашёл занятный видос на ютубе, где рассматривается алгоритмизированный подход в решении задачек на правильную скобочную последовательность, и в нем вводится такое понятие, как стек (stack), в котором мы, при движении по строке слева направо, «кладём» каждую открывающую скобку, и «забираем» по одной открывающей скобке, если нам по ходу движения по строке встречаются закрывающие скобки.

Таким образом, правильная скобочная последовательность для указанной последовательности выше, будет выглядеть так: [((()))(())].

Надеюсь, кому-нибудь это будет полезно.

Answer 2

Если вам надо из неправильной последовательности получить любую правильную удалением / добавлением скобок и при этом у вас только 1 вид скобок (), то вам не нужнен стек, это делается простым счетчиком.

Идея алгоритма в том, чтобы при проходе по строке, считать сколько незакрытых скобок в момент и не допускать закрытых скобок без парных открытых, а в конце закрыть все незакрытое. То есть по сути, этот алгоритм закроет все незакрытые скобки и удалит закрывающие скобки без парных открывающих. Пример

private static String getValidParentheses(String input) {
    int open = 0;
    int ind = 0;

    StringBuilder result = new StringBuilder();

    while (ind < input.length()) {
        char c = input.charAt(ind);
        if (c == '(') {
            open++;
            result.append(c);
        }
        if (c == ')' && open > 0) {
            open--;
            result.append(c);
        }
        ind++;
    }
    while (open > 0) {
        result.append(')');
        open--;
    }
    return result.toString();
}

Проверка

System.out.println(getValidParentheses("((())()(())"));
System.out.println(getValidParentheses("(((()"));
System.out.println(getValidParentheses("())))"));

Вывод

((())()(()))
(((())))
()

Конкретно этот алгоритм самый простой, но если добавить сюда другие типы скобок, то придется да, пользоваться стеком, что тоже не проблема, если вас устроит любое количество изменений в строке.

БЛОГ НА HUSL

Что необходимо изменить в скобочной последовательности [((())()(())]], чтобы она стала правильной?

Ответы (2 шт):