Expression with Balanced Brackets using Stack in C

Back to: Data Structures and Algorithms Tutorials

Expression with Balanced Brackets using Stack in C:

In this article, I will discuss the Expression with Balanced Brackets using a Stack in C Language with Examples. Please read our previous article discussing Parenthesis Matching using Stack in C. In our previous article, we’ve seen the complete program for parenthesis matching. Now, we have a challenge for all the readers. The challenge is an extended version of parenthesis matching. Let us explain the problem to you.

Expression with Balanced Brackets:

This is a parenthesized expression, but it not only has parentheses; different types of brackets are also present, such as square brackets, curly brackets, and round brackets. So, the problem is to check whether these brackets are balanced. Let us examine this expression. This problem can also be solved using a stack. Let’s take a stack, trace this expression, and show you how it should work.

Here, we have an empty stack. Let’s scan each character of the expression.

The first character is an open curly bracket. We’ll push it into the stack.

Next, we encounter two open brackets.

Push these brackets into the stack.

Here, we have three open brackets inside the stack.

Here, we need to ignore these characters as we only take action when we encounter an open or close bracket. So, let’s move forward.

Here, we’ve encountered a closed square bracket. Therefore, when we pop out the last character from the stack, it must match this square bracket. Since the last character in the stack is an open square bracket, it’s a match. We’ll pop it out from the stack.

Let’s move to the next character in the expression.

This character is neither an open nor a closing bracket, so we’ll ignore it and proceed.

This is an open square bracket, so we’ll push it into the stack.

Let’s move further.

Again, we’ll ignore these characters as we don’t need them.

This is a closed square bracket. Therefore, we need to check whether the last element of the stack is an open square bracket. If it is, we’ll pop it out from the stack.

We popped out the open square bracket from the stack. Let’s move further.

This is a closed parenthesis, so we have to match it with the last element of the stack.

We removed the open parenthesis from the stack because it matched the current character of the expression, which is a closed parenthesis.

We don’t need to take action on these characters, so let’s move further.

This is a closed curly bracket. If it is an open curly bracket, we need to pop out the last element from the stack.

So, we removed the open curly bracket from the stack. Now, the stack is empty, indicating that the brackets are balanced. Let’s see another example of a non-balanced bracket.

Expression with Unbalanced Brackets:

In this expression, the brackets are not balanced. Let’s scan this expression. The first three characters are open brackets. So, let’s push them into the stack.

Again, let’s skip these characters.

For this closed parenthesis, we need to pop out the corresponding open parenthesis. However, the last element in the stack is an open square bracket, indicating a mismatch. This extra complexity arises because we need to handle different types of brackets. When pushing a bracket into the stack, we need to check its type. In the previous parenthesis program, we only checked whether the bracket was opened or closed. However, here, we need to distinguish between the types of brackets. Therefore, we have to handle three types of brackets: open curly, open square, and open parenthesis. Similarly, we also need to check for the corresponding types of closing brackets: curly, square, or parenthesis. Thus, instead of checking for one symbol, we now have to check for three symbols.

If the character is in any of those three open brackets, push it. And if the bracket is any of those three close brackets, pop it. Below is a sample pseudocode:

if(exp[i] == '{' || exp[i] == '[' || exp[i] == '('){
    push(&st, exp[i]);
}

If the above condition is satisfied, push the symbol or bracket onto the stack st.

if(exp[i] == '}' || exp[i] == ']' || exp[i] == ')'){
    x = pop(&st);
}

If this condition is satisfied, pop the last character from the stack st. Now, here, you have to check whether this exactly matches the type of bracket or not. Therefore, you have to write the code for this logic. This presents a challenge for students, as they have to consider many scenarios. For example, if the closing bracket is of type parenthesis, then the corresponding open bracket should also be of type parenthesis in order to pop it out.

We are giving you a hint so that you can make it a little simpler.

Here, we have the ASCII codes for those three types of brackets. The ASCII codes for parentheses are 40 and 41, which are below 50. For square brackets, the codes are 91 and 93, and for curly brackets, the codes are 123 and 125. So, if the codes are less than 40, the difference between the codes is 1 (41-40). If they are greater than 90, the difference is 2 (93-91, 125-123). By using this, you can reduce the length of the code. You don’t have to write so many if-else statements. By using this hint, you can write some tricky code to reduce the number of conditional statements. Anyway, if you’re writing many conditional statements, that’ll also be fine.

So, this is a challenge for students. You have to write a program to solve this problem.

In the next article, I will discuss Infix to Postfix Conversion using Stack in C. In this article, I explain Expression with Balanced Brackets using Stack in C Language with Examples. I hope you enjoy this article on Expression with Balanced Brackets.