Check the Balance of Parenthesis in Java

Last Updated on June 1, 2023 by Mayank Dham

To check balanced parentheses is a simple interview question in which we are asked to determine whether or not the given string (of brackets) is balanced. The traditional method is to use stacks, but we can also find it by using standard programming techniques. The different brackets are (), [], and. A question can be asked of any type of bracket or of all types of brackets.

Algorithm to check the Balance of Parenthesis Using Stacks in Java

1. Establish a character stack.
2. Now go through the expression string exp.
3. Push the current character to stack if it is a starting bracket (‘(‘ or ” or ‘[‘)..
4. If the current character is a closing bracket (‘)’, ”, or ‘]’), pop it from the stack; otherwise, if the popped character is the matching starting bracket, the brackets are not balanced.
5. If there is some starting bracket left in the stack after traversal, then "not balanced."

Pseudo code to check the Balance of Parenthesis Using Stacks

function checkBalance():
    create an empty stack 
    read the expression from the user  
    for each character ch in the expression:
        if ch is an opening parenthesis ('(', '{', or '['):
            push ch to the stack
        else if ch is a closing parenthesis (')', '}', or ']'):
            if the stack is empty or the top of the stack does not match the corresponding opening parenthesis for ch:
                print "Unbalanced Parentheses!"
                return
            else:
                pop the top element from the stack

    if the stack is empty:
        print "Balanced Parentheses."

Java code to check the Balance of Parenthesis Using Stacks

import java.util.*;

class Main
{
   public static void main(String[] args)
   {
      String expression;
      int i, length;
      char ch;
      Scanner s = new Scanner(System.in);
      
      System.out.print("Enter the Expression: ");
      expression = s.next();
      
      Stack<Character> stack = new Stack<Character>();
      length = expression.length();
      
      for(i=0; i<length; i++)
      {
         ch = expression.charAt(i);
         if(ch=='(' || ch=='{' || ch=='[')
         {
            stack.push(ch);
         }
         else if(ch==')')
         {
            if(stack.isEmpty() || stack.pop() != '(')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
         else if(ch=='}')
         {
            if(stack.isEmpty() || stack.pop() != '{')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
         else if(ch==']')
         {
            if(stack.isEmpty() || stack.pop() != '[')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
      }
      if(stack.isEmpty())
         System.out.println("\nBalanced Parentheses.");
   }
}

Output

Enter the Expression: {}{}{}
Balanced Parentheses.

Algorithm to check the Balance of Parenthesis without Using Stacks in Java

• Begin with a counter variable ‘count’ set to 0.
• From left to right, traverse each character ‘ch’ in the input expression.
• If ‘ch’ is an opening parenthesis ‘(‘, the ‘count’ is increased by one.
• If ‘ch’ is a closing parenthesis ‘)’, the ‘count’ is decremented by one.
• Check to see if the ‘count’ ever becomes negative during the traversal. If it does, return false to indicate unbalanced parentheses.
• Check if the ‘count’ is equal to 0 after traversing the entire expression. If it is, return true to indicate that the parentheses are balanced. Otherwise, return false.

Pseudo code to check the Balance of Parenthesis without Using Stacks

function checkBalance(expression):
    count = 0
    for each character ch in expression:
        if ch is '(':
            increment count by 1
        else if ch is ')':
            decrement count by 1
            if count < 0:
                return false
    return count is 0

Java code to check the Balance of Parenthesis without Using Stacks

import java.util.Scanner;
class Main
{
   public static void main(String[] args)
   {
      String expression;
      int i, length, j=0, count=0;
      char ch, c;
      char[] stk = new char[20];
      Scanner s = new Scanner(System.in);
      
      System.out.print("Enter the Expression: ");
      expression = s.next();
      
      length = expression.length();
      
      for(i=0; i<length; i++)
      {
         ch = expression.charAt(i);
         if(ch=='(' || ch=='{' || ch=='[')
         {
            stk[j] = ch;
            j++;
            count = 1;
         }
         else if(ch==')')
         {
            if(count==1)
               j--;
            c = stk[j];
            if(stk.length==0 || c != '(')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
         else if(ch=='}')
         {
            if(count==1)
               j--;
            c = stk[j];
            if(stk.length==0 || c != '{')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
         else if(ch==']')
         {
            if(count==1)
               j--;
            c = stk[j];
            if(stk.length==0 || c != '[')
            {
               System.out.println("\nUnbalanced Parentheses!");
               return;
            }
         }
      }
      System.out.println("\nBalanced Parentheses.");
   }
}

Output

Enter the Expression: {}{}{}
Balanced Parentheses.

Conclusion
In programming interviews, checking the balance of parentheses is a common task. Stacks have traditionally been used to solve this problem, but there are other approaches available. This article presented two methods: one that used stacks and one that did not.
Pushing opening parentheses onto the stack and popping matching opening parentheses for closing parentheses is the stack-based approach. If there is a mismatch or the stack is empty, the parentheses are unbalanced. To keep track of opening and closing parentheses, the stack-less approach employs a counter variable. The balance of parentheses is determined by incrementing and decrementing the counter. A negative or non-zero count indicates that the parentheses are unbalanced. For both approaches, pseudo code and Java code examples were provided. The stack-based code made use of the 'Stack' class from 'java.util,' whereas the stack-less code relied on arrays. Both methods work well for checking the balance of parentheses, allowing you to determine whether or not an expression has balanced parentheses. Choose the approach that suits your requirements and coding style.

Frequently Asked Questions (FAQs)

Q1. How do you balance paranthesis?
Given a parenthesized string s that only contains the letters '(' and ')'. A parentheses string is balanced if each left parenthesis '(' has two consecutive right parenthesis '))'. The left parenthesis '(' must come before the two consecutive right parenthesis '))'.

Q2. What is an example of a balanced parentheses?
( 2+5 ) * 4

Q3. What are function balanced parentheses?
Valid brackets (balanced brackets) are a notation used in computer science to simplify expressions typed in an operator-precedence parser by allowing the programmer to explicitly identify a particular expression's operator precedence and associativity.