Balanced Parentheses 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 some kind of 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 really aren't balanced if the brackets enclosing a string are still not matched.
A string that contains non-bracket characters like a-z, A-Z, 0-9, as well as other special characters like #, $, and @ is likewise regarded as unbalanced in this way.
Example “{[(])}”
The two round brackets, "()," encompass a single unbalanced closing square parenthesis, "]," and the two square brackets, "[]," surround a single unbalanced starting round bracket, "(," making it an imbalanced input string.
A bracketed string is considered to also be balanced if:
- Each equivalent opening bracket is followed by a matched closing bracket.
- Balanced brackets also should enclose balanced brackets.
- There shouldn't be any non-bracket characters in it.
Note 1: Null is thought to be in balance.
Note 2: A string that is empty is thought to be balanced.
Algorithm (Deque)
- We create a character stack first.
- input string to character array conversion.
- Explore 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 really aren't 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 with balanced parentheses.
BalancedParenthesesExpl1.java
// import any necessary packages and classes.
import java.util.*;
// To implement Balanced Parentheses using stack,
// create the class BalancedParenthesesExpl1.
public class BalancedParenthesesExpl1 {
// develop a balanced approach
// To determine whether the supplied
// string is balanced, use the function parenthesis().
@SuppressWarnings({ "rawtypes", "unchecked" })
public static boolean balancedParenthesis(String inputStr) {
// creating an empty stack
Stack st = new Stack();
// convert inputStr to char arr
char[] charArr = inputStr.toCharArray();
// iterate charArr
for (int j = 0; j < charArr.length; j++) {
// get c
char c = charArr[j];
// check to see whether c is "(," "[," or ""
if (c == '{' || c == '[' || c == '(') {
// push current to stack
st.push(c);
continue;
}
// Return false if the stack is empty.
if (st.isEmpty()) {
return false;
}
// Use a switch statement to remove an element
// from the stack, and return false if the element is '(', '[', or ".
char pC;
switch (c) {
case ')':
pC = (char) st.pop();
if (pC == '{' || pC == '[')
return false;
break;
case '}':
pC = (char) st.pop();
if (pC == '(' || pC == '[')
return false;
break;
case ']':
pC = (char) st.pop();
if (pC == '(' || pC == '{')
return false;
break;
}
}
return (st.isEmpty());
}
// driver code
public static void main(String[] args) {
String iS;
// create an object for the Scanner class
Scanner s = new Scanner(System.in);
System.out.println("Enter input string to check:");
// taking the input string from the user
iS = s.nextLine();
// To determine whether the supplied string
// is balanced or not, call the balancedParenthesis() function.
if (balancedParenthesis(iS))
System.out.println(" Given Input string "+iS+" is balanced.");
else
System.out.println(" Given Input string "+iS+" is not balanced.");
}
}
Output:
BalancedParenthesesExpl2.java
// import any necessary packages and classes.
import java.util.Scanner;
// To implement Balanced Parentheses using simple for loop,
// create the class BalancedParenthesesExpl2.
public class BalancedParenthesesExpl2 {
// driver code
public static void main(String[] args)
{
String iS;
int j, l, k=0, c=0;
char crr, ch;
// creating an empty stack
char[] st = new char[20];
// create an object for the Scanner class
Scanner s = new Scanner(System.in);
System.out.print("Enter an expression to check whether it is balanced or not: \n");
iS = s.nextLine();
// closing Scanner class instance
s.close();
// get length of iS
l = iS.length();
// using for loop to iterate the input string
for(j = 0; j < l; j++) {
crr = iS.charAt(j);
// check whether crr is '(', '{', or '['
if(crr =='(' || crr =='{' || crr =='[') {
st[k] = crr;
k++; // increase the count of k
c = 1; // set c to 1
} else if(crr == ')') { // if crr char is ')'
if(c == 1) // if c is 1, decrement count of k
k--;
ch = st[k]; // store st[k] to ch
if(st.length == 0 || ch != '(') { // Parentheses are not balanced if st is empty while ch is opening with the letter "("
System.out.println("\nUnbalanced Parentheses!");
return;
}
} else if(crr == '}') { // if crr char is '}'
if(c == 1) // if c is 1, decrement the count of k
k--;
ch = st[k]; // store st[k] to ch
if(st.length == 0 || ch != '{') { // Parentheses are not balanced if st is empty while ch is opening with the letter "{"
System.out.println("\nUnbalanced Parentheses!");
return;
}
} else if(crr == ']') { // if curr char is ']'
if(c == 1) // if c is 1, decrement the count of k
k--;
ch = st[k]; // store st[k] to ch
if(st.length == 0 || ch != '[') { // Parentheses are not balanced if stack is empty while ch is opening with the letter "["
System.out.println("\nUnbalanced Parentheses!");
return;
}
}
}
System.out.println("\nBalanced Parentheses.");
}
} Output:
BalancedParenthesesExpl3.java
// import any necessary packages and classes.
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
// To implement Balanced Parentheses using Deque,
// create the class BalancedParenthesesExpl2.
public class BalancedParenthesesExpl3 {
// Driver Code
public static void main(String[] args)
{
String iS;
// creating an empty deque using LinkedList
Deque<Character> dq = new LinkedList<>();
// create an object for the Scanner class
Scanner s = new Scanner(System.in);
System.out.print(" To determine whether an expression is balanced, enter one:\n ");
iS = s.nextLine();
// closing the Scanner class instance
s.close();
// iterating through the input string using for loop
for(char ch : iS.toCharArray()) {
// add elements to dq if ch = '{', ch = '[', or ch = '('
if(ch == '{' || ch == '[' || ch == '(') {
dq.add(ch);
} else {
// if dq is not empty
if(! dq.isEmpty()) {
if((dq.peekFirst() == '{' && ch == '}')
|| (dq.peekFirst() == '[' && ch == ']')
|| (dq.peekFirst() == '(' && ch == ')')) {
dq.removeFirst();
}
}else {
System.out.println("\nUnbalanced Parentheses.");
}
}
}
System.out.println("\nBalanced Parentheses.");
}
}
Output:
