Balanced Brackets Algorithm in Java – Java中的平衡小括号算法

最后修改: 2020年 1月 24日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

Balanced Brackets, also known as Balanced Parentheses, is a common programming problem.

平衡括号，也被称为平衡括号，是一个常见的编程问题。

In this tutorial, we will validate whether the brackets in a given string are balanced or not.

在本教程中，我们将验证给定字符串中的括号是否平衡。

This type of strings are part of what’s known as the Dyck language.

这种类型的字符串是所谓的Dyck语言的一部分。

2. Problem Statement

2 问题陈述

A bracket is considered to be any of the following characters – “(“, “)”, “[“, “]”, “{“, “}”.

大括号被认为是以下任何一个字符 – “(“, “)”, “[“, “]”, “{“, “}”。

A set of brackets is considered to be a matched pair if an opening bracket, “(“, “[“, and “{“, occurs to the left of the corresponding closing bracket, “)”, “]”,  and “}”, respectively.

如果开头的括号、”(“、”[“和”{“，分别出现在相应的结尾括号、”)”、”]”和”}”的左边，则一组括号被认为是配对的。

However, a string containing bracket pairs is not balanced if the set of brackets it encloses is not matched.

然而，一个包含括号对的字符串，如果它所包围的括号集没有被匹配，则是不平衡的。

Similarly, a string containing non-bracket characters like a-z, A-Z, 0-9 or other special characters like #,$,@ is also considered to be unbalanced.

同样，包含非括号字符的字符串，如a-z、A-Z、0-9或其他特殊字符如#、$、@ 也被认为是不平衡的。

For example, if the input is “{[(])}”, the pair of square brackets, “[]”, encloses a single unbalanced opening round bracket, “(“. Similarly, the pair of round brackets, “()”, encloses a single unbalanced closing square bracket, “]”. Thus, the input string “{[(])}” is unbalanced.

例如，如果输入的是”{[(])}”，这对方括号”[]”包围着一个不平衡的开头圆括号”(“。 同样地，这对圆括号”() “包围着一个不平衡的结尾方括号”]”。因此，输入字符串”{[(])}”是不平衡的。

Therefore, a string containing bracket characters is said to be balanced if:

因此，如果一个包含括号字符的字符串被认为是平衡的。

  1. A matching opening bracket occurs to the left of each corresponding closing bracket
  2. Brackets enclosed within balanced brackets are also balanced
  3. It does not contain any non-bracket characters

There are a couple of special cases to keep in mind: null is considered to be unbalanced, while the empty string is considered to be balanced.

有几个特殊情况要记住。null被认为是不平衡的，而空字符串被认为是平衡的。

To further illustrate our definition of balanced brackets, let’s see some examples of balanced brackets:

为了进一步说明我们对平衡括号的定义，让我们看看一些平衡括号的例子。

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

And a few that are not balanced:

还有一些不平衡的。

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

Now that we have a better understanding of our problem, let’s see how to solve it!

现在我们对我们的问题有了更好的了解，让我们看看如何解决这个问题

3. Solution Approaches

3.解决方案的方法

There are different ways to solve this problem. In this tutorial, we will look at two approaches:

有不同的方法来解决这个问题。在本教程中，我们将看一下两种方法。

  1. Using methods of the String class
  2. Using Deque implementation

4. Basic Setup and Validations

4.基本设置和验证

Let’s first create a method that will return true if the input is balanced and false if the input is unbalanced:

让我们首先创建一个方法，如果输入是平衡的，将返回true，如果输入是不平衡的，将返回false。

public boolean isBalanced(String str)

Let’s consider the basic validations for the input string:

让我们考虑一下输入字符串的基本验证。

  1. If a null input is passed, then it’s not balanced.
  2. 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.
  3. 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.

Given these rules, we can implement the validations:

鉴于这些规则，我们可以实现验证。

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;
        }
    }
}

Now that the input string is validated, we can move on to solving this problem.

现在，输入字符串已被验证，我们可以继续解决这个问题。

5. Using String.replaceAll Method

5.使用String.replaceAll方法

In this approach, we’ll loop through the input string removing occurrences of “()”, “[]”, and “{}” from the string using String.replaceAll. We continue this process until no further occurrences are found in the input string.

在这种方法中，我们将循环浏览输入字符串，使用String.replaceAll.从字符串中删除出现的”()”、”[]”和”{}”，直到输入字符串中不再出现其他出现。

Once the process is complete, if the length of our string is zero, then all matching pairs of brackets have been removed and the input string is balanced. If, however, the length is not zero, then some unmatched opening or closing brackets are still present in the string. Therefore, the input string is unbalanced.

一旦这个过程完成，如果我们的字符串的长度为零，那么所有匹配的括号对已经被删除，输入的字符串是平衡的。然而，如果长度不是零，那么一些不匹配的开头或结尾括号仍然存在于字符串中。因此，输入的字符串是不平衡的。

Let’s see the complete implementation:

让我们看看完整的实现。

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

6. Using Deque

6.使用Deque

Deque is a form of the Queue that provides add, retrieve and peek operations at both ends of the queue. We will leverage the Last-In-First-Out (LIFO) order feature of this data structure to check for the balance in the input string.

Deque是Queue的一种形式，在队列的两端提供添加、检索和窥视操作。我们将利用这种数据结构的后进先出（LIFO）顺序特性来检查输入字符串的平衡。

First, let’s construct our Deque:

首先，让我们构建我们的Deque。

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

Note that we have used a LinkedList here because it provides an implementation for the Deque interface.

注意，我们在这里使用了LinkedList，因为它为Deque接口提供了一个实现。

Now that our deque is constructed, we will loop through each character of the input string one by one. If the character is an opening bracket, then we will add it as the first element in the Deque:

现在我们的deque已经构建完成，我们将逐一循环浏览输入字符串的每个字符。如果该字符是一个开括号，那么我们将把它作为第一个元素添加到Deque中。

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

But, if the character is a closing bracket, then we will perform some checks on the LinkedList.

但是，如果该字符是一个收尾括号，那么我们将对LinkedList执行一些检查。

First, we check whether the LinkedList is empty or not. An empty list means that the closing bracket is unmatched. Therefore, the input string is unbalanced. So we return false.

首先，我们检查LinkedList是否为空。一个空的list意味着结尾的括号是不匹配的。因此，输入的字符串是不平衡的。所以我们返回false。

However, if the LinkedList is not empty, then we peek on its last-in character using the peekFirst method. If it can be paired with the closing bracket, then we remove this top-most character from the list using the removeFirst method and move on to the next iteration of the loop:

然而，如果LinkedList不是空的，那么我们使用peekFirst方法偷看其最后一个字符。如果它能与闭合括号配对，那么我们使用removeFirst方法从list中移除这个最上面的字符，并进入下一个循环的迭代。

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

By the end of the loop, all characters are balance-checked, so we can return true. Below is a complete implementation of the Deque based approach:

在循环结束时，所有的字符都经过了平衡检查，所以我们可以返回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. Conclusion

7.结语

In this tutorial, we discussed the problem statement of Balanced Brackets and solved it using two different approaches.

在本教程中，我们讨论了平衡括号的问题陈述，并使用两种不同的方法解决了它。

As always, the code is available over on Github.

像往常一样，代码可以在Github上获得。