Balanced Parenthesis Problem in Java

Understanding Balanced Parenthesis Problem

The balanced parenthesis problem involves checking whether a given string of brackets is balanced or not.

We will explore three different methods to solve this problem in Java.

Method 1: Using Stack

import java.util.Stack;

public class BalancedParenthesis {
    public static boolean isBalanced(String expr) {
        Stack stack = new Stack<>();
        for (char ch : expr.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                char last = stack.pop();
                if ((ch == ')' && last != '(') || 
                    (ch == '}' && last != '{') || 
                    (ch == ']' && last != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String expr = "{[()]}";
        System.out.println(isBalanced(expr) ? "Balanced" : "Not Balanced");
    }
}
            

Method 2: Using Counter

public class BalancedParenthesisCounter {
    public static boolean isBalanced(String expr) {
        int count = 0;
        for (char ch : expr.toCharArray()) {
            if (ch == '(') count++;
            else if (ch == ')') count--;
            if (count < 0) return false;
        }
        return count == 0;
    }

    public static void main(String[] args) {
        String expr = "(())";
        System.out.println(isBalanced(expr) ? "Balanced" : "Not Balanced");
    }
}
            

Method 3: Recursion

public class BalancedParenthesisRecursion {
    public static boolean checkBalance(String expr, int index, int count) {
        if (count < 0) return false;
        if (index == expr.length()) return count == 0;
        if (expr.charAt(index) == '(') return checkBalance(expr, index + 1, count + 1);
        if (expr.charAt(index) == ')') return checkBalance(expr, index + 1, count - 1);
        return checkBalance(expr, index + 1, count);
    }

    public static void main(String[] args) {
        String expr = "((()))";
        System.out.println(checkBalance(expr, 0, 0) ? "Balanced" : "Not Balanced");
    }
}