Проверка вложенности скобок

22 марта 2021

Содержание

Зачем нужно проверять вложенность скобок
Стек
Реализация
Проверка

Среди алгоритмических задач довольно часто встречается задача на проверку скобочной последовательности. То есть на вход передаётся строка, в которой содержатся символы скобок и, возможно, другие символы. И нужно ответить, правильно ли скобки вложены друг в друга или нет? Иными словами, на каждую открывающую скобку должна приходиться закрывающая скобка.

Зачем нужно проверять вложенность скобок

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

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

Стек

Стек – это такая коллекция объектов, в которой первым извлекается последний добавленный объект (т.н. LIFO – «last in, first out»). В Java есть такой класс как Stack, однако это класс, а не интерфейс, а программировать нужно на уровне интерфейсов, поэтому использовать его не рекомендуется. Вместо этого возьмём интерфейс Deque – коллекцию, которая поддерживает удаление и вставку с обоих концов. В качестве реализации этого интерфейса возьмём LinkedList.

Более подробно см. в статье Коллекции: очередь и стек.

Реализация

Теперь перейдём к реализации нашего метода проверки isValidBrackets(). Метод принимает строку, содержащую скобки и возвращает true – если вложенность скобок правильная. Сначала определим соответствие каждой открывающей и закрывающей скобки.

private static boolean isValidBrackets(String input) {
    Map<Character, Character> brackets = new HashMap<>();
    brackets.put(')', '(');
    brackets.put('}', '{');
    brackets.put(']', '[');

Мы создаём мапу, в которой ключом является именно закрывающая скобка, а значением – открывающая, т.к. соответствие нужно вычислять именно для закрывающей.

Далее создаём наш стек на базе LinkedList.

Deque<Character> stack = new LinkedList<>();
for (char c : input.toCharArray()) {
    if (brackets.containsValue(c)) {
        // одна из открывающих скобок
        stack.push(c);
    } else if (brackets.containsKey(c)) {
        // одна из закрывающих скобок
        if (stack.isEmpty() || stack.pop() != brackets.get(c)) {
            return false;
        }
    }
}
// в конце стек должен быть пустым
return stack.isEmpty();

Затем в цикле проходимся по каждому символу строки и проверяем, если это это открывающая скобка (метод мапы containsValue()), то просто добавляем его в стек с помощью метода push(). Если же это закрывающая скобка (метод containsKey()), то стек должен быть не пустым и последним добавленным в него элементом должна быть открывающая скобка такого же типа.

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