Braces Problem in Java
One of the frequent programming issues, commonly referred to as the Balanced brackets issue, is the problem with the balanced parenthesis. Interviewers frequently provide this task, in which we must determine whether or not the brackets in a given string are balanced.
- Brackets include symbols like "(", "")", "[", "]", "," and "."
- If the starting bracket appears to the left of the equivalent closing bracket, then the group of parentheses is said to be matched.
- Bracket pairs are not balanced if the brackets enclosing a string are not matched.
- A string that contains non-bracket characters like a-z, A-Z, 0-9, and other special characters like #, $, and @ is likewise regarded as unbalanced in this way.
Ex. "[(])" is an uneven input string because the pair of round brackets, "()," encompass a single unbalanced closing square bracket, "]," and the pair of square brackets, "[]," enclose a single unbalanced starting round bracket, "(."
When a bracketed string is balanced, it means that:
- To the right of each corresponding opening bracket is a matching closing bracket.
- The brackets encircling balanced brackets must likewise be balanced.
- No non-bracket characters are allowed in it.
Algorithm (Deque)
- We declare a character stack first.
- input string to character array conversion.
- Go through the input string (By traversing the character array).
- If the current character is a starting bracket ('(', ", or '['), we push it to the stack.
- If the current character is a closing bracket, we pop it off the stack. The brackets are not balanced if the character that pops out doesn't match the initial bracket.
- The brackets are not balanced once the traversal is complete and some initial brackets are still present in the stack.
- Stack, Deque, and a straightforward for loop can be used to build the code for balanced parentheses.
How to implement balanced parentheses in Java?
There are several ways to implement balanced parentheses in Java, including using a stack or a regular expression. Here we will show how to use a stack to check for balanced parentheses.
First, we need to create a stack that will hold the opening parentheses. We will then loop through the input string, adding each opening parenthesis to the stack and removing each closing parenthesis from the stack. If the stack is empty at the end of the loop, it means that all the parentheses were properly matched.
Here is an example of how to implement balanced parentheses using a stack in Java:
BalancedParentheses.java
import java.util.Stack;
public class BalancedParentheses {
public static boolean isBalanced(String input) {
Stack<Character> stack = new Stack<Character>();
for (char c : input.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
String input = "((3 + 4) * 5)";
boolean result = isBalanced(input);
System.out.println(result);
}
}
Output:
true
In the above example, we first create a stack of characters called stack. We then loop through the input string input, checking each character to see if it is an opening parenthesis ('(', '[', or '{') or a closing parenthesis (')', ']', or '}').
If the character is an opening parenthesis, we push it onto the stack. If the character is a closing parenthesis, we first check if the stack is empty. If the stack is empty, it means that there is no corresponding opening parenthesis, so we return false. Otherwise, we pop the top character from the stack and check if it matches the closing parenthesis. If the opening and closing parentheses do not match, we return false.
At the end of the loop, we check if the stack is empty. If the stack is empty, it means that all the parentheses were properly matched, so we return true. Otherwise, we return false.
Complexity
The time complexity of this algorithm is O(n), where n is the length of the input string. This is because we iterate through the string once, and each operation of pushing or popping from the stack takes constant time.