«1. Обзор
Сбалансированные скобки, также известные как Сбалансированные скобки, являются распространенной проблемой программирования.
В этом уроке мы проверим, сбалансированы ли скобки в заданной строке.
Этот тип строк является частью так называемого языка Дайка.
2. Постановка задачи
Скобкой считается любой из следующих символов – “(“, “)”, “[“, “ ]», «{», «}».
Набор скобок считается совпадающей парой, если слева от соответствующую закрывающую скобку, «)», «]» и «}», соответственно.
Однако строка, содержащая пары квадратных скобок, не сбалансирована, если набор заключенных в нее скобок не совпадает.
Точно так же строка, содержащая символы без квадратных скобок, такие как a-z, A-Z, 0-9 или другие специальные символы, такие как #, $, @, также считается несбалансированной.
Например, если введено «{[(])}» , пара квадратных скобок «[]» заключает в себя одну несбалансированную открывающую круглую скобку «(» œ Аналогично, пара круглых скобок \»()\» заключает в себя одну несбалансированную закрывающую квадратную скобку \»]\». Таким образом, входная строка \»{[(])}\» равна
Таким образом, строка, содержащая символы квадратных скобок, называется сбалансированной, если:
- A matching opening bracket occurs to the left of each corresponding closing bracket
- Brackets enclosed within balanced brackets are also balanced
- It does not contain any non-bracket characters
Следует помнить о нескольких особых случаях: нуль считается несбалансированным, а пустая строка считается сбалансированной. .
Чтобы проиллюстрировать наше определение сбалансированных скобок, давайте рассмотрим несколько примеров сбалансированных скобок:
()
[()]
{[()]}
([{{[(())]}}])И несколько несбалансированных скобок:
abc[](){}
{{[]()}}}}
{[(])}Теперь, когда мы лучше понимаем нашу Проблема, давайте посмотрим, как ее решить!
3. Подходы к решению
Существуют разные способы решения этой проблемы. В этом руководстве мы рассмотрим два подхода:
- Using methods of the String class
- Using Deque implementation
4. Базовая настройка и проверки ~~ ~ Давайте сначала создадим метод, который будет возвращать true если ввод сбалансирован и ложен, если ввод несбалансирован:
Давайте рассмотрим основные проверки входной строки:
public boolean isBalanced(String str)Учитывая эти правила, мы можем реализовать проверки:
- If a null input is passed, then it’s not balanced.
- For a string to be balanced, the pairs of opening and closing brackets should match. Therefore, it would be safe to say that an input string whose length is odd will not be balanced as it will contain at least one non-matched bracket.
- As per the problem statement, the balanced behavior should be checked between brackets. Therefore, any input string containing non-bracket characters is an unbalanced string.
Теперь, когда входная строка проверена, можно переходить к решению этой задачи.
if (null == str || ((str.length() % 2) != 0)) {
return false;
} else {
char[] ch = str.toCharArray();
for (char c : ch) {
if (!(c == '{' || c == '[' || c == '(' || c == '}' || c == ']' || c == ')')) {
return false;
}
}
}5. Использование метода String.replaceAll
В этом подходе мы будем перебирать входную строку, удаляя вхождения «()», «[]» и «{} — из строки с помощью String.replaceAll. Мы продолжаем этот процесс до тех пор, пока во входной строке не будет найдено больше вхождений.
После завершения процесса, если длина нашей строки равна нулю, все совпадающие пары скобок удаляются, и входная строка сбалансирована. Если же длина не равна нулю, то в строке все же присутствуют непарные открывающие или закрывающие скобки. Следовательно, входная строка несбалансирована.
Давайте посмотрим на полную реализацию:
6. Использование Deque
while (str.contains("()") || str.contains("[]") || str.contains("{}")) {
str = str.replaceAll("\\(\\)", "")
.replaceAll("\\[\\]", "")
.replaceAll("\\{\\}", "");
}
return (str.length() == 0);Deque — это форма очереди, которая обеспечивает операции добавления, извлечения и просмотра на обоих концах очереди. Мы будем использовать функцию сортировки «последним пришел – первым вышел» (LIFO) этой структуры данных, чтобы проверить баланс во входной строке.
Сначала создадим наш Deque:
Обратите внимание, что здесь мы использовали LinkedList, потому что он обеспечивает реализацию интерфейса Deque.
Deque<Character> deque = new LinkedList<>();Теперь, когда наша двухсторонняя очередь построена, мы будем перебирать каждый символ входной строки один за другим. Если символ является открывающей скобкой, то мы добавим его первым элементом в Deque:
Но, если символ является закрывающей скобкой, то мы выполним некоторые проверки в LinkedList.
if (ch == '{' || ch == '[' || ch == '(') {
deque.addFirst(ch);
}Сначала мы проверяем, пуст ли LinkedList. Пустой список означает, что закрывающая скобка не имеет соответствия. Следовательно, входная строка несбалансирована. Поэтому мы возвращаем false.
Однако, если LinkedList не пуст, мы просматриваем его последний символ, используя метод peekFirst. Если он может быть сопряжен с закрывающей скобкой, то мы удаляем этот самый верхний символ из списка с помощью метода removeFirst и переходим к следующей итерации цикла:
«
if (!deque.isEmpty()
&& ((deque.peekFirst() == '{' && ch == '}')
|| (deque.peekFirst() == '[' && ch == ']')
|| (deque.peekFirst() == '(' && ch == ')'))) {
deque.removeFirst();
} else {
return false;
}«К концу цикла все символы проверяются на баланс, поэтому мы можем вернуть true. Ниже приведена полная реализация подхода на основе Deque:
Deque<Character> deque = new LinkedList<>();
for (char ch: str.toCharArray()) {
if (ch == '{' || ch == '[' || ch == '(') {
deque.addFirst(ch);
} else {
if (!deque.isEmpty()
&& ((deque.peekFirst() == '{' && ch == '}')
|| (deque.peekFirst() == '[' && ch == ']')
|| (deque.peekFirst() == '(' && ch == ')'))) {
deque.removeFirst();
} else {
return false;
}
}
}
return true;7. Заключение
В этом уроке мы обсудили постановку задачи Balanced Brackets и решили ее, используя два разных подхода.
Как всегда, код доступен на Github.