Java Coding Challenge - Stack of Curly Braces

Introduction

Balancing curly braces ({}) is a common problem in coding interviews, especially when validating strings with nested or paired braces. In this challenge, we will check if a given string of curly braces is balanced using a stack.

A string is considered balanced if:

• Every opening brace { has a corresponding closing brace }.
• The braces are properly nested.

Example:

• Input: "{{}}{}"

• Output: "Balanced"

• Input: "{{}{"

• Output: "Not Balanced"

In this blog post, we will write a Java program that checks whether a given string of curly braces is balanced using a stack.

Problem Statement

You are given a string containing only curly braces ({ and }). Your task is to determine if the string is balanced. A string is balanced if:

1. Every opening brace { has a corresponding closing brace }.
2. Braces are properly nested.

Example:

• Input: "{{}}{}"

• Output: "Balanced"

• Input: "{{}{"

• Output: "Not Balanced"

Approach

Steps:

1. Use a Stack: Push each opening brace { onto the stack. For every closing brace }, pop from the stack and check if it matches the last opened brace.
2. Check Conditions:
   • If you encounter a closing brace but the stack is empty, the string is not balanced.
   • After processing all characters, if the stack is not empty, the string is not balanced.
3. Final Result: If all opening braces have matching closing braces, the string is balanced.

Java Code

import java.util.Stack;

public class BraceChecker {
    
    // Method to check if curly braces are balanced
    public static boolean isBalanced(String str) {
        // Create a stack to hold the opening braces
        Stack<Character> stack = new Stack<>();
        
        // Traverse each character in the string
        for (char c : str.toCharArray()) {
            if (c == '{') {
                // Push opening brace to the stack
                stack.push(c);
            } else if (c == '}') {
                // If stack is empty, it means there's no corresponding opening brace
                if (stack.isEmpty()) {
                    return false; // Not balanced
                }
                // Pop the matching opening brace
                stack.pop();
            }
        }

        // If stack is empty at the end, all braces were balanced
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String input1 = "{{}}{}";
        String input2 = "{{}{";
        
        System.out.println("Input: " + input1 + " -> " + (isBalanced(input1) ? "Balanced" : "Not Balanced"));
        System.out.println("Input: " + input2 + " -> " + (isBalanced(input2) ? "Balanced" : "Not Balanced"));
    }
}

Explanation:

Step 1: Initialize the Stack

We create a Stack<Character> to store the opening curly braces {.

Stack<Character> stack = new Stack<>();

Step 2: Traverse the String

We loop through each character in the input string. If we encounter an opening brace {, we push it onto the stack. For a closing brace }, we check whether there is a corresponding opening brace in the stack.

for (char c : str.toCharArray()) {
    if (c == '{') {
        stack.push(c);
    } else if (c == '}') {
        if (stack.isEmpty()) {
            return false; // No matching opening brace
        }
        stack.pop(); // Pop the matching opening brace
    }
}

Step 3: Final Stack Check

After traversing the string, if the stack is empty, it means every opening brace { had a matching closing brace }. If the stack is not empty, there are unmatched opening braces, so the string is not balanced.

return stack.isEmpty();

Usage Example:

public static void main(String[] args) {
    String input1 = "{{}}{}";
    String input2 = "{{}{";
    
    System.out.println("Input: " + input1 + " -> " + (isBalanced(input1) ? "Balanced" : "Not Balanced"));
    System.out.println("Input: " + input2 + " -> " + (isBalanced(input2) ? "Balanced" : "Not Balanced"));
}

Output:

Input: {{}}{} -> Balanced
Input: {{}{ -> Not Balanced

Explanation of Output:

• Input: "{{}}{}" -> All opening braces have matching closing braces, so the string is Balanced.
• Input: "{{}{ -> One opening brace { is left unmatched, so the string is Not Balanced.

Time Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate over each character in the string once.
• Space Complexity: O(n) in the worst case, where all characters are opening braces and are stored in the stack.

Conclusion

In this blog post, we have implemented a solution to check if a string of curly braces is balanced using a stack in Java. The stack follows the LIFO (Last In, First Out) principle, which helps efficiently match opening and closing braces. This solution runs in O(n) time and is a common approach for solving similar problems involving paired or nested elements, such as parentheses, brackets, or HTML tags.