Java program to check the balance of parenthesis

August 23, 2021

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

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