Checking if brackets or parentheses are "balanced" is one of the most popular questions in coding interviews. It is a fundamental problem used to check if mathematical expressions or code structures (like in Java or HTML) are correctly written.

To solve this, we use a special storage structure called a Stack. Let's explore how it works using a simple toy analogy.

Illustration of nesting dolls and open/closed brackets
Real-World Analogy: Nesting Russian Dolls

Imagine you have a set of nesting Russian dolls. Each doll has a **bottom half** (an opening bracket like (, [, or {) and a **top half** (a closing bracket like ), ], or }).

When you assemble the dolls:

  • Every time you pick up a bottom half, you place it on your workspace table (we **push** it onto the Stack).
  • Every time you pick up a top half, you must match it with the **most recent** bottom half you placed on the table (we look at the top of the Stack).
  • If they match, you put them together and set them aside (we **pop** the bottom half off the Stack).
  • If they don't match, or if you run out of bottom halves on the table, the nesting is broken!

Walkthrough of the Main Method Scenario

Let's trace how the program executes step-by-step from the entry point of the main method:

Step 1: Setting up the pattern and the Stack

The program declares our target string pattern and creates an empty Stack:

String paranthesisPattern = "[()()]{}(){}";
Stack<Character> stack = new Stack<>();

This pattern contains a mix of square brackets, parentheses, and curly braces.

Step 2: Processing each character

The program loops through the characters in the array:

  • Character 1 ([): It is an opening bracket. The program pushes it onto the Stack. Stack state: [ '[' ].
  • Character 2 ((): It is an opening parenthesis. Push it. Stack state: [ '[', '(' ].
  • Character 3 ()): It is a closing parenthesis. The program checks the top of the stack ((). It matches, so we pop the top off the stack. Stack state: [ '[' ].
  • Character 4 ((): Opening parenthesis. Push it. Stack state: [ '[', '(' ].
  • Character 5 ()): Closing parenthesis. Match and pop. Stack state: [ '[' ].
  • Character 6 (]): Closing square bracket. The program checks the top of the stack ([). It matches, so pop. Stack state: [] (empty).

The loop continues for the remaining characters { } ( ) { }, which all pair up perfectly and leave the stack empty.

Step 3: Verification

After checking all characters, if the Stack size is 0, the pattern is well-formed:

if (stack.size() == 0) {
    System.out.println("Well formed paranthesis");
}

Since all brackets opened and closed in the correct nesting order, our program prints: "Well formed paranthesis".

Java Implementation

Below is the complete Java code demonstrating parenthetical validation using a Stack:

package io.practise.accolite;
 
import java.util.Stack;
 
public class ParenthesisChecker {
 
    public static void main(String[] args) {
 
        String paranthesisPattern = "[()()]{}(){}";
 
        Stack stack = new Stack<>();
 
        char arr[] = paranthesisPattern.toCharArray();
 
        for (int i = 0; i < arr.length; ++i) {
            char ch = arr[i];
 
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')') {
                if (stack.isEmpty()) {
                    stack.push(ch); // push to signal incorrect count
                    break;
                }
                Character tempCh = stack.peek();
 
                if (tempCh != '(') {
                    break;
                } else {
                    stack.pop();
                }
            } else if (ch == '}') {
                if (stack.isEmpty()) {
                    stack.push(ch);
                    break;
                }
                Character tempCh = stack.peek();
 
                if (tempCh != '{') {
                    break;
                } else {
                    stack.pop();
                }
            } else if (ch == ']') {
                if (stack.isEmpty()) {
                    stack.push(ch);
                    break;
                }
                Character tempCh = stack.peek();
 
                if (tempCh != '[') {
                    break;
                } else {
                    stack.pop();
                }
            }
        }
 
        if (stack.size() == 0) {
            System.out.println("Well formed paranthesis");
        } else {
            int output = arr.length - stack.size();
            System.out.println("parenthesis not correct it's correct for upto these characters: " + output);
        }
 
    }
}

Conclusion

The Stack structure is perfect for balanced parenthesis validation because it enforces the "Last-In, First-Out" (LIFO) rule. The bracket that opens last must close first, just like nesting Russian dolls inside one another!