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.

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

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