Balanced Parentheses | Brackets - Solution in Java

Java program to check whether a string is valid or not if it contains nested parentheses.

Balanced Brackets or Balanced Parentheses is a Java problem. You could have heard or seen this problem on many online coding problem platforms like hacker rank and leetcode.

Problem Description 

The “(“, “)”, “[“, “]”, “{“, “}” are considered to be the possible bracket pairs. Based on the above bracket pairs, a string is said to be a balanced bracket.

If the opening brackets "(", "[", and "{" appear to the left of the closing brackets ")", "]", and "}" of the same type.

For example. if the given string is "{[]}", the pair of "{}" contains a subset of brackets enclosed within it "[]" since all the pairs of the bracket have matching opening and closing brackets. Thus it's balanced.

A string is said to be an unbalanced bracket when any one of the following conditions is met.

1. If the string is null.
2. If the string length is odd then it means it doesn't contain matching closed or opening brackets.
3. If it has any unmatched brackets.

For example, if the input is “{[(]]}”, contains a pair of curly brackets "{}" and it contains a pair of square brackets "[]" within which again the square brackets contain a sub bracket which is "(]" but now the sub brackets do not have matching opening and closing brackets, therefore the input "{[(]]}" is unbalanced.

If the given string is balanced return true(YES) otherwise false(NO).

Below are some examples of balanced brackets.

"()"

"()[]{}"

"{[()]}"

Below are some examples of unbalanced brackets.

"(]"

"{[(])}"      

"{{{[]}}}}"   

Implementing Algorithm

The problem can be solved in various ways. We will discuss two different approaches in this tutorial:

• Using String Replace and Regular Expression
• Using Stack

Using String ReplaceAll with Regular Expression

The Java String.replaceAll() method is used to replace the old value or substring with new values.

We can either specify the old value or give an expression. The method evaluates regular expressions to search for matches. If the string content matches the expression, replace it with an empty string.

1. Loop through the string. 
2. If the string contains any brackets pairs like "()", "[]" and "{}"
3. Replace the content using String.replaceAll() with an empty value.
4. Repeat steps 2 and 3 until the string has no brackets left.
5. If the string length is zero, it means the string is balanced and all bracket pairs have been removed.
6. If the string length is not zero, it means the string is unbalanced. It has some opening and closing brackets left.

public static boolean isBalanced(String str) {

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

Using Stack

Let's say we are given parentheses or expressions, and we need to determine whether they are balanced. The stack can help us perform this check.

The stack data structure uses the last-in-first-out (LIFO) principle. This means that the last element inserted into the stack is removed first.

In Java, the Stack class is present inside the collection framework which provides all stack operations such as push (insert) and pop (remove).

1. Loop through the string.
2. If the character is a bracket such as "[","{" and "(" then insert it into the stack.
3. If the character is a closing bracket such as "]","{" and ")" then remove the element from the stack.
1. If the stack is empty, the string is unbalanced it has an unmatched closing operation.
2. If the stack is not empty, check whether the current closing bracket has the matching opening bracket (value pop from the stack).
• Removed element from stack == "{" and character == "}"
• Removed element from stack == "[" and character == "]"
• Removed element from stack == "(" and character == ")"
4. After the loop has completed, check if the string is empty.
5. If the string is empty, then the input is balanced. Otherwise, it contains some unmatched brackets.

import java.util.Stack;

public class StringBracker {

	public static void main(String[] args) {
		System.out.println(isBalanced("{[()]}"));
		System.out.println(isBalanced("{{[[(())]]}}"));
		System.out.println(isBalanced("{}[]()"));
        System.out.println(isBalanced("{[(])}"));
	}

	public static boolean isBalanced(String str) {
		Stack<Character> stack = new Stack<>();
		char[] letters = str.toCharArray();

		for (Character bracket: letters) {
			if (isOpeningBracket(bracket)) {
				stack.push(bracket);
			} else {
				if (!stack.empty()) {
					char openBracket = stack.pop();
					if (checkBracket(openBracket, bracket)) {
						continue;
					} else {
						return false;
					}
				} else {
					return false;
				}
			}
		}

		return stack.isEmpty();
	}

	public static boolean checkBracket(char openBracket, char closeBracket) {

		if (openBracket == '{' && closeBracket == '}') {
			return true;
		} else if (openBracket == '[' && closeBracket == ']') {
			return true;
		} else if (openBracket == '(' && closeBracket == ')') {
			return true;
		} else {
			return false;
		}
	}

	public static boolean isOpeningBracket(char bracket) {
		return bracket == '{' || bracket == '(' || bracket == '[';
	}
}

For more practice try to solve out below problems. 

Coding Bat String Problems and Solutions

Coding Bat Advanced String Problems and Solutions

Coding Bat Array Problems and Solutions

Java interview Coding round questions and solution - string