One of the interesting java program given below that may be asked in core java interview or the same may be given to students to solve at practical labs
Write a java program that reads a string (expression) from standard input and find whether its parentheses "(" , ")" , brackets "[", "]" and Braces "{", "}" are properly balanced or not. i.e. Every open parentheses"(" , braces "{" and brackets "[" should have closing parenthesis ")" , braces "}" and brackets "]" respectively in the right order . For example, the program will give output
true for the following input
1. ((29*12)+(54+22))
Please assume that , '(' , '{' , '[' are open characters and ')' , '}' , ']' are closing characters . Let us solve the above problem now.
.
Method I : Best way to solve the above problem is using stack data structure . As we know , stack is a storage mechanishm that works on Last -in-First-Out (LIFO) that means the last item stored on the stack is the first one to be removed. For more on Stack , please visit my earlier tutorial Stack a FIFO data structure
How to solve the above problem using stack ?
1) Read the input string (expression ) from the keyboard
2) Create a stack object to accept character only.
3. Traverse the input string / expression
a) If the current character is a open (left ) parenthesis '(' or brace '{' or bracket '[' then push the corresponding closing (right) character (i.e. ')' , '}' , ']') to the stack. You can push the open chracters. I have Pushed the closing charaters to the stack instead of left to reduce the little bit lines of logic.
b) If the current character is a closing (right) parenthesis ')' , brace '}' and bracket ']' ,
i) check for the stack is empty , if it is empty , then the parentheses are not balanced because there is no open characters for the corresponding closing charaters.
ii) if stack is not empty , then check the current character with top character (get the top character using peek() ) in the stack . If both are equal, then pop the character from the stack and check for the next character.
4) Once the traversal of the expression is completed , check for the stack is empty or not . If stack is empty , then parentheses are balanced otherwise not balanced.
The code is as follows .
Some of the other tries to solve the above program.
Method II using Regular expression (Regex) . You can also try without using regex . I have used very simple regex . Steps to solve the above problem are as follows.
1. Remove all characters like digits , operators, etc except '(', ')' , '{', '}' , '[' , ']' in the expression.
2. Replace every occurrence of '()' , '{}' , '[]' in the string with empty string ("") (i.e removal of characters)
3. Repeat the step 2 , until you find that nothing has been replaced .
4. Now check for the expression is empty or not. If the string is empty , then parentheses are perfectly balanced , otherwise not.
Code is as follows
Method III : Using counter . But this method is not suitable for all situations . It just checks , whether the expression has equal number of opening and closing parentheses or brackets or braces and does not check the order. For example, consider the following expression.
([{)}]
The above expression has the equal number of opening and closing parentheses / brackets / braces . But it is not in the right order. The right order may be ([{}])
This method may be suitable , if you use either parentheses or brackets or braces in the expression. eg. ((()(()()))) . Otherwise the order should be correct, if you use all .
Steps :
1. Initialize three counters to 0 , one for parentheses, one for braces , and one for bracket
2. Traverse the expression by a single character at a time.
a) If the current character is '(' , '{' , '[' , then increment the respective counter by one
b) If the current character is ')', '}' , ']' , then decrease one from the respective counter variable.
3. Check whether all the counters are zero or not. If all counters are having 0 , then the parentheses are balanced , otherwise not . Please always remember limitation using this method.
Code is as follows.
Write a java program that reads a string (expression) from standard input and find whether its parentheses "(" , ")" , brackets "[", "]" and Braces "{", "}" are properly balanced or not. i.e. Every open parentheses"(" , braces "{" and brackets "[" should have closing parenthesis ")" , braces "}" and brackets "]" respectively in the right order . For example, the program will give output
true for the following input
1. ((29*12)+(54+22))
2. {[()()]()}
3. ((([]{}))((())))
and false for the following
1. [(]).
2. ((())))
3. ((29*12*([5*5+7]*5)) + ((54+22))
Please assume that , '(' , '{' , '[' are open characters and ')' , '}' , ']' are closing characters . Let us solve the above problem now.
.
Method I : Best way to solve the above problem is using stack data structure . As we know , stack is a storage mechanishm that works on Last -in-First-Out (LIFO) that means the last item stored on the stack is the first one to be removed. For more on Stack , please visit my earlier tutorial Stack a FIFO data structure
How to solve the above problem using stack ?
1) Read the input string (expression ) from the keyboard
2) Create a stack object to accept character only.
3. Traverse the input string / expression
a) If the current character is a open (left ) parenthesis '(' or brace '{' or bracket '[' then push the corresponding closing (right) character (i.e. ')' , '}' , ']') to the stack. You can push the open chracters. I have Pushed the closing charaters to the stack instead of left to reduce the little bit lines of logic.
b) If the current character is a closing (right) parenthesis ')' , brace '}' and bracket ']' ,
i) check for the stack is empty , if it is empty , then the parentheses are not balanced because there is no open characters for the corresponding closing charaters.
ii) if stack is not empty , then check the current character with top character (get the top character using peek() ) in the stack . If both are equal, then pop the character from the stack and check for the next character.
4) Once the traversal of the expression is completed , check for the stack is empty or not . If stack is empty , then parentheses are balanced otherwise not balanced.
The code is as follows .
import java.util.Stack;
import java.util.Scanner;
public class Parentheses1 {
public static boolean isBalanced1(String exp) {
Stack<Character> stack = new Stack<Character>();
for (int i=0; i<exp.length(); i++) {
char c = exp.charAt(i);
switch (c) {
case '{' : stack.push('}'); break;
case '(' : stack.push(')'); break;
case '[' : stack.push(']'); break;
case ']' : case ')' : case '}' :
if (stack.isEmpty())
return false;
else if (stack.peek() == c) {
stack.pop();
}
break;
default : break;
}
}
return stack.isEmpty();
}
Some of the other tries to solve the above program.
Method II using Regular expression (Regex) . You can also try without using regex . I have used very simple regex . Steps to solve the above problem are as follows.
1. Remove all characters like digits , operators, etc except '(', ')' , '{', '}' , '[' , ']' in the expression.
2. Replace every occurrence of '()' , '{}' , '[]' in the string with empty string ("") (i.e removal of characters)
3. Repeat the step 2 , until you find that nothing has been replaced .
4. Now check for the expression is empty or not. If the string is empty , then parentheses are perfectly balanced , otherwise not.
Code is as follows
public static boolean isBalanced2(String exp) {
String temp="";
while (exp.trim().length() > 0 )
{
exp=exp.replaceAll("[^\\(\\)\\[\\]\\{\\}]", "") ;
exp=exp.replaceAll("\\(\\)", "");
exp=exp.replaceAll("\\{\\}", "");
exp=exp.replaceAll("\\[\\]", "");
if (exp.trim().equals(temp)) break;
temp=exp;
}
if ( exp.trim().length() ==0) return true;
else {
System.out.println("Unmatched / Unbalanced characters " + exp);
return false;
}
}
Method III : Using counter . But this method is not suitable for all situations . It just checks , whether the expression has equal number of opening and closing parentheses or brackets or braces and does not check the order. For example, consider the following expression.
([{)}]
The above expression has the equal number of opening and closing parentheses / brackets / braces . But it is not in the right order. The right order may be ([{}])
This method may be suitable , if you use either parentheses or brackets or braces in the expression. eg. ((()(()()))) . Otherwise the order should be correct, if you use all .
Steps :
1. Initialize three counters to 0 , one for parentheses, one for braces , and one for bracket
2. Traverse the expression by a single character at a time.
a) If the current character is '(' , '{' , '[' , then increment the respective counter by one
b) If the current character is ')', '}' , ']' , then decrease one from the respective counter variable.
3. Check whether all the counters are zero or not. If all counters are having 0 , then the parentheses are balanced , otherwise not . Please always remember limitation using this method.
Code is as follows.
public static boolean isBalanced3(String exp) {
int c1=0, c2=0,c3=0;
for (int i=0; i<exp.length(); i++) {
char c = exp.charAt(i);
switch (c) {
case '{' : c1++; break;
case '(' : c2++; break;
case '[' : c3++; break;
case '}' : c1--; break;
case ')' : c2--; break;
case ']' : c3--; break;
default : break;
}
}
if(c1==0 && c2==0 && c3==0) return true;
else return false;
}
//Main Method to call the above three methods
public static void main(String[] args) {
Scanner sc=new Scanner(System.in).useDelimiter("\n");;
String s = sc.next();
System.out.println("Balanced checking using stack " + isBalanced1(s));
System.out.println("Balanced checking using regex " + isBalanced2(s));
System.out.println("Balanced checking using counter " + isBalanced3(s));
}
}
