Статьи
YouTube-канал

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

22 марта 2021

Тэги: Java Java 8 алгоритмы головоломки

Содержание

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

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

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

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

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

Стек

Стек - это такая коллекция объектов, в которой первым извлекается последний добавленный объект (т.н. 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()), то стек должен быть не пустым и последним добавленным в него элементом должна быть открывающая скобка такого же типа.

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

Проверка

Теперь проверим работу нашего метода на конкретных примерах:

public static void main(String[] args) {
    System.out.println(isValidBrackets("")); // 1 - true
    System.out.println(isValidBrackets("(abc)")); // 2 - true
    System.out.println(isValidBrackets("(({}[()]))")); // 3 - true
    System.out.println(isValidBrackets("(()")); // 4 - false
    System.out.println(isValidBrackets("((]")); // 5 - false
    System.out.println(isValidBrackets("]")); // 6 - false
}
  1. true - т.к. входная строка вообще не содержит никаких символов.
  2. true - в строке содержатся помимо скобок и другие символы, но вложенность правильная
  3. true - несколько разных видов скобок, но вложенность правильная
  4. false - не хватает ещё одной круглой закрывающей скобки
  5. false - встретили закрывающую квадратную скобку, но ожидаем круглую
  6. false - в строке сразу встретили закрывающую квадратную скобку

При обработке слишком длинной строки имеет смысл обрабатывать её в буферизованном потоке.


Облако тэгов

Kotlin, Java, Java 16, Java 11, Java 10, Java 9, Java 8, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Hibernate, Collections, Stream API, многопоточность, ввод-вывод, Apache, maven, gradle, JUnit, YouTube, новости, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml

Последние статьи


Комментарии

Добавить комментарий

×

devmark.ru