Program for Balanced Parenthesis problem in Java

May 18, 2022

Balanced Parenthesis Problem

Today in this article we will learn how to solve Balanced Parenthesis problem.

Lets understand this with the help of an example:-

Input: str = “[{}]”
Output: balanced

Algorithm

Initialize a character stack st
Now traverse the string s
If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack st.
If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then check if the st is empty or not and also check if the top of the stack is the same opening brackets if it’s true then pop from stack otherwise put ans = false and break.
At last check if stack is empty or not if its not empty return false
At the end of the function return ans.
In the main function inside if function check the string and print if the string is balanced or not

Java Code :-

Run

import java.util.*;
public class Main {

 static boolean areBracketsBalanced(String expr)
 {
  // Using ArrayDeque is faster than using Stack class
  Deque<Character> stack = new ArrayDeque<Character>();

  // Traversing the Expression
  for (int i = 0; i < expr.length(); i++)
  {
   char x = expr.charAt(i);
   if (x == '(' || x == '[' || x == '{')
   {
     // Push the element in the stack
     stack.push(x);
     continue;
   }

  if (stack.isEmpty())
    return false;
  char check;
  switch (x) {
   case ')': check = stack.pop();
   if (check == '{' || check == '[')
     return false;
     break;

   case '}': check = stack.pop();
   if (check == '(' || check == '[')
    return false; 
    break;

   case ']': check = stack.pop();
    if (check == '(' || check == '{')
      return false;
    break;
   }
 }

  // Check Empty Stack
  return (stack.isEmpty());
 } 

// Driver code
  public static void main(String[] args)
 {
  String expr = "([{}])";

  // Function call
  if (areBracketsBalanced(expr))
    System.out.println("Balanced ");
  else
    System.out.println("Not Balanced ");
  }
 }

Output:-

Balanced