Java program to check the balance of parenthesis

Balanced Parenthesis

To check balanced parenthesis is a basic interview question where we are asked to find whether the given string(of brackets) is balanced or not. To do this , the traditional way of doing is using stacks but we can also find by using normal programming techniques. Different brackets are  ( ) , [ ] , { }. Question can be asked on any type of bracket or of all types of brackets.

  • Sample input: ()(())
  • Sample output: True
Balanced Parenthesis in Java

Algorithm

  • Declare a character stack.
  • Now traverse the expression string exp. 
    1. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
    2. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else brackets are not balanced.
  • After complete traversal, if there is some starting bracket left in stack then “not balanced”

Code in Java

import java.util.*;
public class Main{

public static boolean balancedParenthesis(String str)
{

Stack<Character> stack= new Stack<Character>();

for (int i = 0; i < str.length(); i++)
{
char x = str.charAt(i);
if (x == '(' || x == '[' || x == '{')
{
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;
}
}
return (stack.isEmpty());
}

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String str=sc.next();
if (balancedParenthesis(str))
System.out.println("True");
else
System.out.println("False");
}
}

Output :

()(())

True