1. Overview
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.
2. Problem Statement
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.
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:
- 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
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.
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
There are different ways to solve this problem. In this tutorial, we will look at two approaches:
- Using methods of the String class
- Using Deque implementation
4. Basic Setup and Validations
Let’s first create a method that will return true if the input is balanced and false if the input is unbalanced:
public boolean isBalanced(String str)
Let’s consider the basic validations for the input string:
- 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.
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
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.
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
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.
First, let’s construct our Deque:
Deque<Character> deque = new LinkedList<>();
Note that we have used a LinkedList here because it provides an implementation for the Deque interface.
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:
if (ch == '{' || ch == '[' || ch == '(') {
deque.addFirst(ch);
}
But, if the character is a closing bracket, then we will perform some checks on the 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.
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:
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:
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
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.