How to check parentheses in a string / exp. are balanced using Regex / Stack ?

One of the interesting  java program  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))
              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 mechanism that works on  Last -in-First-Out (LIFO) that means  the last item stored on the stack  is the first one to be removed.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 characters.   I have Pushed the closing characters 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 characters.
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));

}

} 

Output:

Wrong output when using Counter for the following input 

You may also like

Leave a Reply