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

1. Обзор

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

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

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

2. Постановка задачи

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

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

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

Точно так же строка, содержащая символы без квадратных скобок , такие как az, AZ, 0-9 или другие специальные символы, такие как #, $, @ , также считается несбалансированной .

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

Следовательно, строка, содержащая символы квадратных скобок, называется сбалансированной, если:

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

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

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

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

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

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

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

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

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

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

4. Базовая настройка и проверки

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

public boolean isBalanced(String str)

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

1. Если передается нулевой вход, то он не сбалансирован.
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 — это форма очереди , которая обеспечивает операции добавления, извлечения и просмотра на обоих концах очереди. Мы будем использовать функцию сортировки « последним пришел – первым вышел» (LIFO) этой структуры данных, чтобы проверить баланс во входной строке.

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

Deque<Character> deque = new LinkedList<>();

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

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

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

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

Во-первых, мы проверяем, является ли 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 deque.isEmpty();

7. Заключение

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

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