Java program to check the balance of parenthesis

March 30, 2022

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.

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

Run

import java.util.*;
public
class Main {
    public
    static boolean balancedParenthesis(String str) {
        Stack stack = new Stack();
        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) {
        String str = "()(())";
        if (balancedParenthesis(str))
            System.out.println("True");
        else
            System.out.println("False");
    }
}

Output :

True