Статьи Утилиты Telegram YouTube RuTube Отзывы

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

Видеогайд

22 марта 2021

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

Содержание

  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, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.

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


Комментарии

09.10.2022 17:35 Vitalik

нихуя не понятно,но хоть так

12.10.2022 10:03

Круто, спасибо !

22.10.2022 15:19 Maksel

почему не стоит использовать класс Stack?

22.10.2022 18:02 devmark

Stack - это класс, а не интерфейс, а программировать нужно на уровне интерфейсов. В Java есть ещё один устаревший тип коллекций - это Vector. От которого, кстати, Stack и наследуется. Ну и плюс они оба менее производительны за счёт использования synchronized.

23.12.2022 16:27 Малыш

Автор, спасибо за статью! Материал хорошо структурирован, все четко и по делу.

Правда, я не до конца понял, как работает следующая строчка кода: stack.pop() != brackets.get(c)...
Например, почему при "(()" мы не попадаем в "return false"? Какие скобки сравниваются в этом случае?
Открывающая скобка "(" не равна закрывающей скобке ")", следовательно, мы можем выполнить строку "return false". Или... Сравнивается открывающая скобка "(" c открывающей скобкой "(", поэтому мы не можем выполнить строку "return false"?
Надеюсь, мой вопрос понятен, и Вы сможете на него ответить.
P.S. Я ещё австралопитек по части Java, поэтому хотел бы, чтобы меня просветили.

23.12.2022 16:55 devmark

Постараюсь объяснить. brackets - это мапа, в которой ключом является закрывающая скобка, а значением - парная ей открывающая. brackets.get(c) - тут мы по закрывающей берём эталонную открывающую. затем эту открывающую сравниваем с последней открывающей, помещённой в стек. Они должны быть одинаковыми.

23.02.2023 22:51 Андрей

Метод не рабочий, в таком варианте:
System.out.println(isCorrectParentheses("[]{}(<)>")); //-> false
не отрабатывает. Возвращает true

23.02.2023 22:58 Андрей

Извиняюсь, метод рабочий, просто голова уже кипит)) Автору Респект

24.02.2023 20:05 devmark

Андрей, в любом случае спасибо за обратную связь! Для других добавлю, что в примере Андрея "[]{}(<)>" строка содержит угловые скобки, которые надо добавить в мапу brackets, чтобы метод работал корректно:
brackets.put('>', '<');

06.09.2023 10:35 Иван

Вот так не сработает на сколько я понимаю
System.out.println(isCorrectParentheses("[}"));

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

×

devmark.ru