Задачи со скобками

Стек хранит незакрытые скобки

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

static boolean isValid(String text) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char ch : text.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);
            continue;
        }

        if (stack.isEmpty()) {
            return false;
        }

        char open = stack.pop();
        if ((ch == ')' && open != '(')
                || (ch == ']' && open != '[')
                || (ch == '}' && open != '{')) {
            return false;
        }
    }

    return stack.isEmpty();
}

Почему одной проверки количества недостаточно

Строка "([)]" содержит одинаковое число открывающих и закрывающих скобок, но порядок неправильный: круглая скобка пытается закрыться, пока сверху стека находится квадратная. Стек хранит именно структуру вложенности, а не просто счётчик.

Две типичные ошибки

Если закрывающая скобка приходит при пустом стеке, ей нечего закрывать — строка неверна сразу. Если после обработки всей строки стек не пуст, часть открывающих скобок так и не получила пару. Обе проверки обязательны.

Каждый символ обрабатывается один раз, поэтому временная сложность равна O(n), а дополнительная память в худшем случае — O(n).