How to Check Well-Formatted Brackets in Expressions | Coding Guide

A simple program to check the pair of brackets using Stack in Java, Python, and C#.1 min


Check-Pair-of-Brackets-Well-Formatted-in-an-Expression

Learn how to check well-formatted bracket pairs in expressions with our step-by-step coding guide.

This is a favorite question for interviewers, so prepare it before appearing for the interview.

Cover Image Credits: Check Bracket Pairs using Stack | Image by Rakshit Shah (Author)

Problem: Check Bracket Pairs/Balanced parenthesis using Stack.

Check out the below expression, write a program to check whether started bracket ends or not. Order of Brackets like, ‘[’,’]’,‘{’,’}’, ‘(’,’)’ must be correct, then print “Paired”; otherwise, “Not Paired”.

Input: [({})]

Output: Paired

Input: [(){]

Output: Not Paired

Logic Brainstorming 🧠⚡💡

Define your Algorithm and Steps to implement

First, we need one Stack (LIFO — Last In First Out), where we can push and pop the characters one by one.

How to Create a Stack in Java?

we must import java.util.stack package and use the Stack() constructor of this class

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

We will loop the Input expression and read each character inside a for loop.

In the initial stage, the stack will be empty and we will loop a string containing expressions.

Then we will check, if it is starting bracket like ‘[’,’{’,’(’ — any of them, then push it into the stack.

If we have a closing bracket, then we will compare it with the stack using the pop() method. If the current character matches with the same kind then we will continue and check the next remaining characters; otherwise, break it and print output as “Not Paired”.

I heard that Image says thousands of words.

Let me add one image to tell you the above steps with some visualization.

Algorithm to check bracket balance using stack data file structure | Image by Author

Implementation 💡

Now let’s implement the above-mentioned approach.

1. Code for Java using Stack

// Easy Java program for Bracket Pairs checking
import java.util.*;
 
public class BracketPairsChecker {
 
    // Method to check if brackets have complete pair or not.
    public static boolean areBracketsPaired(String expr)
    {
        // Using ArrayDeque is faster than using Stack class
        Deque stack
            = new ArrayDeque();
 
        // Traversing the Expression
        for (int i = 0; i < expr.length(); i++)
        {
            char x = expr.charAt(i);
 
            if (x == '(' || x == '[' || x == '{')
            {
                // Push the element in the stack
                stack.push(x);
                continue;
            }
 
            // If current character is not opening bracket, then it must be closing. So stack cannot be empty at this point.
            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;
            }
        }
 
        // Check Empty Stack
        return (stack.isEmpty());
    }
 
    // Main method to check the code.
    public static void main(String[] args)
    {
        String expr = "[({})]";
        // String expr = "[(){]";
 
        // Function call
        if (areBracketsPaired(expr))
            System.out.println("Paired");
        else
            System.out.println("Not Paired");
    }
}

Output: Paired ✅

Time Complexity: O(n)

Auxiliary Space: O(n) for the stack.

2. Code for Python using Stack

#Easy python3 program to check whether brackets are paired or not.
def areBracketsPaired(expr):
    stack = []
 
    # Traversing the Expression
    for char in expr:
        if char in ["(", "{", "["]:
 
            # Push the element in the stack
            stack.append(char)
        else:
 
            # IF current character is not opening bracket, then it must be closing.So stack cannot be empty at this point.
            if not stack:
                return False
            current_char = stack.pop()
            if current_char == '(':
                if char != ")":
                    return False
            if current_char == '{':
                if char != "}":
                    return False
            if current_char == '[':
                if char != "]":
                    return False
 
    # Check Empty Stack
    if stack:
        return False
    return True
 
 
# Driver Code
if __name__ == "__main__":
    expr = "[(){]"
 
    # Function call
    if areBracketsPaired(expr):
        print("Paired")
    else:
        print("Not Paired")

Output: Not Paired ✅

Time Complexity: O(n)

Auxiliary Space: O(n) for the stack.

3. Code for C# using Stack

// Easy C# program for checking Brackets parenthesis.
using System;
using System.Collections.Generic;
 
public class BalancedBrackets {
    public class stack {
        public int top = -1;
        public char[] items = new char[100];
 
        public void push(char x)
        {
            if (top == 99)
            {
                Console.WriteLine("Stack full");
            }
            else {
                items[++top] = x;
            }
        }
 
        char pop()
        {
            if (top == -1)
            {
                Console.WriteLine("Underflow error");
                return '';
            }
            else
            {
                char element = items[top];
                top--;
                return element;
            }
        }
 
        Boolean isEmpty()
        {
            return (top == -1) ? true : false;
        }
    }
 
    // Returns true if character1 and character2 are matching left and right brackets
    static Boolean isMatchingPair(char character1,
                                  char character2)
    {
        if (character1 == '(' && character2 == ')')
            return true;
        else if (character1 == '{' && character2 == '}')
            return true;
        else if (character1 == '[' && character2 == ']')
            return true;
        else
            return false;
    }
 
    // Return true if expression has balanced Brackets
    static Boolean areBracketsBalanced(char[] exp)
    {
        // Declare an empty character stack */
        Stack st = new Stack();
 
        // Traverse the given expression to check matching brackets
        for (int i = 0; i < exp.Length; i++)
        {
            // If the exp[i] is a starting bracket then push it
            if (exp[i] == '{' || exp[i] == '('
                || exp[i] == '[')
                st.Push(exp[i]);
 
            //  If exp[i] is an ending bracket then pop from stack and check if the popped bracket is a matching pair
            if (exp[i] == '}' || exp[i] == ')'
                || exp[i] == ']') {
 
                // If we see an ending bracket without a pair then return false
                if (st.Count == 0)
                {
                    return false;
                }
 
                // Pop the top element from stack, if it is not a pair brackets of character then there is a mismatch. This happens for expressions like {(})
                else if (!isMatchingPair(st.Pop(),
                                         exp[i])) {
                    return false;
                }
            }
        }
 
        // If there is something left in expression then there is a starting bracket without a closing bracket
 
        if (st.Count == 0)
            return true; // balanced
        else
        {
            // not balanced
            return false;
        }
    }
 
    public static void Main(String[] args)
    {
        char[] exp = { '[', '(', '{', '}', ')', ']' };
 
        // Function call
        if (areBracketsPaired(exp))
            Console.WriteLine("Paired");
        else
            Console.WriteLine("Not Paired");
    }
}

Output: Paired ✅

Time Complexity: O(n)

Auxiliary Space: O(n) for the stack.

4. Code for C

#include 
#include 
#define bool int
 
// structure of a stack node
struct sNode {
    char data;
    struct sNode* next;
};
 
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data);
 
// Function to pop an item from stack
int pop(struct sNode** top_ref);
 
// Returns 1 if character1 and character2 are matching left
// and right Brackets
bool isMatchingPair(char character1, char character2)
{
    if (character1 == '(' && character2 == ')')
        return 1;
    else if (character1 == '{' && character2 == '}')
        return 1;
    else if (character1 == '[' && character2 == ']')
        return 1;
    else
        return 0;
}
 
// Return 1 if expression has balanced Brackets
bool areBracketsPaired(char exp[])
{
    int i = 0;
 
    // Declare an empty character stack
    struct sNode* stack = NULL;
 
    // Traverse the given expression to check matching
    // brackets
    while (exp[i])
    {
        // If the exp[i] is a starting bracket then push
        // it
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
            push(&stack, exp[i]);
 
        // If exp[i] is an ending bracket then pop from
        // stack and check if the popped bracket is a
        // matching pair*/
        if (exp[i] == '}' || exp[i] == ')'
            || exp[i] == ']') {
 
            // If we see an ending bracket without a pair
            // then return false
            if (stack == NULL)
                return 0;
 
            // Pop the top element from stack, if it is not
            // a pair bracket of character then there is a
            // mismatch.
            // his happens for expressions like {(})
            else if (!isMatchingPair(pop(&stack), exp[i]))
                return 0;
        }
        i++;
    }
 
    // If there is something left in expression then there
    // is a starting bracket without a closing
    // bracket
    if (stack == NULL)
        return 1; // balanced
    else
        return 0; // not balanced
}
 
// Driver code
int main()
{
    char exp[100] = "[({})]";
 
    // Function call
    if (areBracketsPaired(exp))
        printf("Paired n");
    else
        printf("Not Paired n");
    return 0;
}
 
// Function to push an item to stack
void push(struct sNode** top_ref, int new_data)
{
    // allocate node
    struct sNode* new_node
        = (struct sNode*)malloc(sizeof(struct sNode));
 
    if (new_node == NULL) {
        printf("Oh No! n");
        getchar();
        exit(0);
    }
 
    // put in the data
    new_node->data = new_data;
 
    // link the old list off the new node
    new_node->next = (*top_ref);
 
    // move the head to point to the new node
    (*top_ref) = new_node;
}
 
// Function to pop an item from stack
int pop(struct sNode** top_ref)
{
    char res;
    struct sNode* top;
 
    // If stack is empty then error
    if (*top_ref == NULL) {
        printf("Oh No n");
        getchar();
        exit(0);
    }
    else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}

Output: Paired ✅

Time Complexity: O(n)

Auxiliary Space: O(n) for the stack.

Wrapping up...

Hope this article must be helpful for you. If you find joy in what I am doing please give some claps, do some comments and follow me for more upcoming knowledgeable articles.

Read the below articles also: [HIGHLY RECOMMENDED]

1) When to use Interface and Abstract class

2) Top 45+ Collections Java Interview questions

3) How HashMap Works Internally?

4) How HashSet Works Internally?

adsense


Discover more from 9Mood

Subscribe to get the latest posts sent to your email.


Like it? Share with your friends!

What's Your Reaction?

Lol Lol
0
Lol
WTF WTF
0
WTF
Cute Cute
0
Cute
Love Love
1
Love
Vomit Vomit
0
Vomit
Cry Cry
0
Cry
Wow Wow
1
Wow
Fail Fail
0
Fail
Angry Angry
0
Angry
Rakshit Shah

Legend

Hey Moodies, Kem chho ? - Majama? (Yeah, You guessed Right! I am from Gujarat, India) 25, Computer Engineer, Foodie, Gamer, Coder and may be a Traveller . > If I can’t, who else will? < You can reach out me by “Rakshitshah94” on 9MOodQuoraMediumGithubInstagramsnapchattwitter, Even you can also google it to see me. I am everywhere, But I am not God. Feel free to text me.

0 Comments

Leave a Reply

Choose A Format
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Ranked List
Upvote or downvote to decide the best list item
Open List
Submit your own item and vote up for the best submission
Countdown
The Classic Internet Countdowns
Meme
Upload your own images to make custom memes
Poll
Voting to make decisions or determine opinions
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Personality quiz
Series of questions that intends to reveal something about the personality
is avocado good for breakfast? Sustainability Tips for Living Green Daily Photos Taken At Right Moment