Рубрики
Без рубрики

Алгоритм сбалансированных скобок в Java

Научитесь проверять наличие сбалансированных скобок в Java.

Автор оригинала: baeldung.

1. Обзор

Сбалансированные скобки, также известные как сбалансированные скобки, являются распространенной проблемой программирования.

В этом уроке мы проверим, сбалансированы ли скобки в данной строке или нет.

Этот тип строк является частью так называемого языка Dyck .

2. Постановка проблемы

Скобкой считается любой из следующих символов– “(“, “)”, “[“, “]”, “{“, “}”.

Набор скобок считается совпадающей парой, если открывающая скобка , “(“, “[“, и “{“, встречается слева от соответствующей закрывающей скобки , “)”, “]”, и “}”, соответственно.

Однако строка, содержащая пары скобок, не сбалансирована, если набор скобок, которые она заключает, не соответствует .

Аналогично, строка, содержащая символы без скобок , такие как a-z, A-Z, 0-9 или другие специальные символы, такие как#,$,@ , также считается несбалансированной .

Например, если ввод “{[(])}”, пара квадратных скобок” [] ” заключает одну несбалансированную открывающую круглую скобку “(“. Аналогично, пара круглых скобок “() ” заключает одну несбалансированную закрывающую квадратную скобку “]”. Таким образом, входная строка “{[(])}” несбалансирована.

Поэтому строка, содержащая символы в скобках, считается сбалансированной, если:

  1. Слева от каждой соответствующей закрывающей скобки находится соответствующая открывающая скобка
  2. Скобки, заключенные в сбалансированные скобки, также сбалансированы
  3. Он не содержит никаких символов без скобок

Есть несколько особых случаев, которые следует иметь в виду: null считается несбалансированным, в то время как пустая строка считается сбалансированной .

Чтобы проиллюстрировать наше определение сбалансированных скобок, давайте рассмотрим некоторые примеры сбалансированных скобок:

()
[()]
{[()]}
([{{[(())]}}])

И некоторые из них не сбалансированы:

abc[](){}
{{[]()}}}}
{[(])}

Теперь, когда мы лучше понимаем нашу проблему, давайте посмотрим, как ее решить!

3. Подходы к решению

Существуют различные способы решения этой проблемы. В этом уроке мы рассмотрим два подхода:

  1. Использование методов класса String
  2. Использование Deque реализация

4. Основные настройки и проверки

Давайте сначала создадим метод, который будет возвращать true , если входные данные сбалансированы, и false , если входные данные несбалансированы:

public boolean isBalanced(String str)

Давайте рассмотрим основные проверки для входной строки:

  1. Если передается вход null , то он не сбалансирован.
  2. Чтобы строка была сбалансирована, пары открывающих и закрывающих скобок должны совпадать. Поэтому можно с уверенностью сказать, что входная строка, длина которой нечетна, не будет сбалансирована, поскольку она будет содержать по крайней мере одну несогласованную скобку.
  3. В соответствии с постановкой задачи сбалансированное поведение должно быть проверено в скобках. Поэтому любая входная строка, содержащая символы без скобок, является несбалансированной строкой.

Учитывая эти правила, мы можем реализовать проверки:

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 . Мы продолжаем этот процесс до тех пор, пока во входной строке не будет найдено никаких новых вхождений.

После завершения процесса, если длина нашей строки равна нулю, все соответствующие пары скобок были удалены, и входная строка сбалансирована. Если, однако, длина не равна нулю, то некоторые несопоставимые открывающие или закрывающие скобки все еще присутствуют в строке. Таким образом, входная строка несбалансирована.

Давайте посмотрим на полную реализацию:

while (str.contains("()") || str.contains("[]") || str.contains("{}")) {
    str = str.replaceAll("\\(\\)", "")
      .replaceAll("\\[\\]", "")
      .replaceAll("\\{\\}", "");
}
return (str.length() == 0);

6. Использование Deque

Deque – это форма Очереди , которая обеспечивает операции добавления, извлечения и просмотра на обоих концах очереди. Мы будем использовать функцию Last-In-First-Out (LIFO) order этой структуры данных для проверки баланса во входной строке.

Во-первых, давайте построим наш Deque :

Deque deque = new LinkedList<>();

Обратите внимание, что мы использовали здесь Связанный список , потому что он обеспечивает реализацию интерфейса Deque .

Теперь, когда наш deque построен, мы будем перебирать каждый символ входной строки один за другим. Если символ является открывающей скобкой, то мы добавим его в качестве первого элемента в Deque :

if (ch == '{' || ch == '[' || ch == '(') { 
    deque.addFirst(ch); 
}

Но, если символ является закрывающей скобкой, то мы выполним некоторые проверки в Связанном списке .

Сначала мы проверяем, является ли Связанный список пустым или нет. Пустой список означает, что закрывающая скобка не имеет аналогов. Таким образом, входная строка несбалансирована. Поэтому мы возвращаем false .

Однако, если Связанный список не пуст, то мы заглядываем в его последний символ, используя метод peekFirst . Если он может быть сопряжен с закрывающей скобкой, то мы удаляем этот самый верхний символ из списка с помощью метода removeFirst и переходим к следующей итерации цикла:

if (!deque.isEmpty() 
    && ((deque.peekFirst() == '{' && ch == '}') 
    || (deque.peekFirst() == '[' && ch == ']') 
    || (deque.peekFirst() == '(' && ch == ')'))) { 
    deque.removeFirst(); 
} else { 
    return false; 
}

К концу цикла все символы проверяются на баланс, поэтому мы можем вернуть true . Ниже приводится полная реализация подхода, основанного на Deque :

Deque 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. Заключение

В этом уроке мы обсудили постановку проблемы сбалансированных скобок и решили ее с использованием двух различных подходов.

Как всегда, код доступен на Github .

Читайте ещё по теме: