Checking for Balanced Parentheses in a String - A Stack-Based Approach

Problem: Given a string consisting of small, curly, and big parentheses, check whether the parentheses are balanced or not.

Input: string = "([])" Output: 1

Input: string = "(()))" Output: 0

Approach: A string has balanced parentheses if each open parenthesis is closed first and the number of opening parentheses of a particular type is equal to the number of closing parentheses of the same type.

Step 1: Declare a stack of characters.

Step 2: Traverse the given expression, and if the character is an open parenthesis, push it onto the stack.

Step 3: If the character is a closed parenthesis, check if the stack top is an open parenthesis of the same type. If yes, then remove that character from the stack; otherwise, return false.

Step 4: Finally, check if the stack is empty or not. If it is empty, return 1; otherwise, return 0, indicating that there are still unclosed parentheses.

Here's the Java code for the solution:

import java.util.*;

class BalancedParentheses { static boolean isMatching(char a, char b) { if(a == '(' && b == ')') return true;

java
if(a == '[' && b == ']')
        return true;
    
    if(a == '{' && b == '}')
        return true;
    
    return false;
}

static boolean isBalanced(String str) {
    Deque<Character> stack = new ArrayDeque<Character>();
    
    for(int i = 0; i < str.length(); i++) {
        char x = str.charAt(i);
        
        if(x == '(' || x == '{' || x == '[')
            stack.push(x);
        else {
            if(stack.isEmpty())
                return false;
            else if(!isMatching(stack.peek(), x))
                return false;
            else
                stack.pop();
        }
    }
    
    return stack.isEmpty();
}

public static void main(String[] args) {
    String str = "{(())}";
    System.out.println(isBalanced(str)); // true
}

}

The time complexity of this algorithm is O(N), where N is the length of the input string. The auxiliary space used is also O(N) due to the stack used to store the parentheses.