check parentheses in a string / expression are balanced using Regex / Stack . Find Brackets are matched or not in JAVA Program

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))

               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));

    }

}