Parenthesis Matching using Stack in C

Back to: Data Structures and Algorithms Tutorials

Parenthesis Matching using Stack in C:

In this article, we will discuss one of the applications of stack, i.e., Parenthesis Matching using Stack in C with Examples. Please read our previous article discussing Stack Operation using Linked List in C. One common application of the stack is parenthesis matching. Let us explain the problem.

We are given a parenthesis expression. Round brackets are referred to as parentheses, making it a parenthesis expression. Now, we must determine whether the parentheses are balanced, meaning that for every opening parenthesis, there must be a corresponding closing parenthesis, and likewise for opening and closing brackets. This is what we aim to verify. How can we accomplish this? We can utilize a stack to check for balance. Let’s explore how we can use the stack to determine whether the parentheses are balanced.

Implementing Stack to find whether the parenthesis is balanced or not:

Case 1: Parenthesis is matching

Let’s begin with an empty stack. We’ll then proceed to scan through the given expression, taking one symbol or character at a time. Let’s commence scanning.

This is the first character, an open parenthesis. Therefore, we will push it onto the stack.

If it’s an opening bracket, push it onto the stack.

This is ‘a’. Since it’s neither an opening nor a closing bracket, we ignore it and move ahead. In other words, we only need to respond if we encounter an opening or closing bracket. Let’s proceed to the next symbol.

This is a plus symbol. We’ll move ahead.

This is ‘b’. Again, we move ahead.

Now, we encounter a closing parenthesis. What should we do when we encounter a closing bracket? Whenever we encounter a closing bracket, we pop a bracket from the stack. However, we don’t push the closing bracket itself into the stack. The presence of a closing bracket indicates that we have found a match, as there is a corresponding opening bracket in the stack. Therefore, we pop the opening bracket from the stack.

Now that our stack is empty, let’s move to the next symbol in our expression.

This is an asterisk symbol. Therefore, we move ahead.

This is an opening parenthesis that we will push onto the stack.

Now, let’s move to the next symbol. The next symbols are ‘c’ and then a minus symbol. We ignore both of these symbols.

Since this character is neither an opening nor a closing bracket, let’s move to the next character.

Now, we encounter a closing bracket. We should pop a symbol from the stack. After popping the symbol, our stack is empty.

Now, we have reached the end of the given expression, and our stack is empty. This indicates that the parentheses are matching. Let’s consider another example where the parentheses will not match.

Case 2: Parenthesis is not matching

Here, as you can see, we have added one more opening bracket at the start of the expression. So, there are 2 opening brackets and one closing bracket. Now, our stack is empty. Let’s begin scanning this expression.

The first character is an opening bracket. So, we push it onto the stack.

The bracket has been pushed into the stack.

Again, it’s an opening bracket. So, we push it into the stack.

Now, the stack contains two open parentheses. Let’s move to the next symbol.

Here, we’ve skipped the symbols ‘a’, ‘+’, and ‘b’ because we don’t need them for this task.

This is a closed parenthesis. Therefore, we pop the symbol from the stack.

We’ve reached the end of the expression. After popping out the open parenthesis, the stack still contains one open parenthesis. Therefore, there is no match found. Since the stack is not empty, the parentheses are not balanced. Hence, the expression is not balanced. Let’s consider one more example where the expression is not balanced.

As you can see, this expression contains one opening bracket and two closing brackets. Therefore, it is not a balanced expression, or we can say the parentheses are not balanced.

The first symbol is an opening parenthesis that we will push onto the stack.

Here, we skipped ‘a’, ‘+’, and ‘b’ as they are not needed. Now, the arrow is pointing at a closed parenthesis, so we have to pop the symbol from the stack.

Here, our stack is empty. Let’s move to the next bracket symbol.

Here, the arrow is pointing at a closing parenthesis. When we encounter a closing bracket, we pop a value from the stack. However, in this case, the stack is already empty. Therefore, no match was found for this closing bracket.

From our observation, if we scan through an expression by pushing opening brackets onto the stack and popping them out when we encounter closing brackets, then at the end, if the stack is empty, the parentheses are perfectly matched. However, if there is any opening bracket remaining in the stack or if there is a closing bracket in the expression but the stack is empty, the expression or parentheses are not balanced. So, there are two situations when the parentheses do not match.

Condition for Unbalanced Expression:

The first situation occurs when you finish the procedure, but there is still an opening bracket in the stack. The second situation arises when you attempt to pop out a symbol, but the stack is already empty. Now, let’s look at the example below.

This expression is not properly parenthesized. Parenthesization typically involves enclosing operands and operators within brackets to indicate the scope of an operation. In this case, we have an operand and an operator (a +) enclosed in brackets. However, the second operand is outside the bracket. This does not constitute proper parenthesization. Nevertheless, let’s check whether the parentheses are balanced or not.

Push the opening bracket into the stack.

Since it’s a closing bracket, we pop from the stack. Now, the stack becomes empty.

Once more, push the opening bracket into the stack.

Here, we remove the opening bracket from the stack, which makes the stack empty. This indicates that the parentheses match.

Program for Parenthesis Matching in C:

Now, we will write a program for parenthesis matching.

We have this expression represented as an array of characters. This array is terminated by the null character ‘\0’, making it a string. Now, let’s create a function called ‘isBalance (char *exp)’. This function will check whether the expression has balanced parentheses or not. If it is balanced, the function will return true; otherwise, it will return false. The function takes a parameter (char *exp), which is a pointer to a character, allowing it to access the array of characters. A pointer to an array works just like the name of an array. Now, let’s write the procedure.

Creating a function to check the parenthesis balance:

First, we need a stack so that we will use a stack of type array. For that, we will define a structure.

struct Stack {
  int size;
  int top;
  char * S;
};

We have created this structure in our previous articles on the stack. You can check those to get the full context.

struct Stack st;

“st” is a variable of type Stack. Since we have an array of characters, the stack will also be of characters. Therefore, we have changed the data type of the stack to characters. As you can see, our Stack structure has three parameters: size, top, and *S (a pointer to a character).

How to initialize a Stack?

To initialize the stack ‘st’, we need to set the size of the stack and the top pointer. The size of the stack depends on the number of open brackets, as we are only pushing open brackets onto the stack. How do we determine the number of open brackets? We’ll assume that the maximum number of open brackets will be equal to the size of the expression. Therefore, we will use a stack size equal to the size of the expression. However, to do this, we need to know the length of the string or expression.

st.size = strlen (exp);

st.top = -1;

Here, we have set the size of the stack as the length of the given expression. To achieve this, we used the strlen function, which gives us the length of the given string. Then, we set the top pointer to -1. Now, we need to create an array of the given size. Therefore, we will create an array dynamically.

st.S = new char [st.size];

Here, we have created an array of characters with the given size, i.e., st.size. Now, let’s visualize the structure inside the memory.

This is the structure of the Stack that we have created. However, a simplified version of the stack structure is:

This diagram should suffice for our understanding; we don’t need to view the complete structure of the stack memory. It’s provided here for your reference. Let’s proceed.

Now, we need to scan through the given expression by examining one character at a time, starting from the 0th index until we reach null. To achieve this, we will use a for loop to access the expression.

for(i = 0; exp[i] != '
for(i = 0; exp[i] != '\0'; i++){
if (exp[i] == '(')
push(&st, exp[i]);
else if(exp[i] == ')'){
if(isEmpty(st)) 
return false;
pop(&st);
}
}
'; i++){
    if (exp[i] == '(')
        push(&st, exp[i]);
    else if(exp[i] == ')'){
        if(isEmpty(st)) 
            return false;
        pop(&st);
    }
}

This loop will scan the expression starting from the 0th index, incrementing it to access each character until it reaches null. Inside this loop, we use an if-else statement. In the if part, if exp[i] is equal to an open bracket, i.e., ‘(‘ , we push it onto the stack. Push (&st, exp[i]) will push the character present at the ith index into the stack. We call st with a reference here because we’re modifying the stack. In the else part, if exp[i] is equal to a close bracket, i.e., ‘)’, we’ll pop it out. However, before popping out, we need to check if the stack is empty. If the stack is empty, i.e., if (isEmpty(st)), we return false. If the stack isn’t empty, we’ll pop out the character or open bracket from the stack. The Pop function takes the address of st because it modifies the stack by popping out the character from it.

That’s the simplest logic. We only need to take action if we encounter an open or close bracket; otherwise, we move forward in the expression. Once the control exits the for loop, it indicates that the entire expression has been scanned. After scanning, there should be nothing remaining inside the stack.

return isEmpty(st)? true:false;

At the end of the function, we need to check whether the stack is empty. If it is, we return true; otherwise, we return false.

Complete Program of Parenthesis Checking in C Language:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Stack {
  int size;
  int top;
  int * S;
};

void create(struct Stack * st) {
  printf("Enter Size: ");
  scanf("%d", & st -> size);
  st -> top = -1;
  st -> S = (int * ) malloc(st -> size * sizeof(int));
}

void Display(struct Stack st) {
  int i;
  for (i = st.top; i >= 0; i--)
    printf("%d ", st.S[i]);
  printf("\n");
}

void push(struct Stack * st, int x) {
  if (st -> top == st -> size - 1)
    printf("Stack overflow\n");
  else {
    st -> top++;
    st -> S[st -> top] = x;
  }
}

int pop(struct Stack * st) {
  int x = -1;

  if (st -> top == -1)
    printf("Stack Underflow\n");
  else {
    x = st -> S[st -> top--];
  }
  return x;
}

int peek(struct Stack st, int index) {
  int x = -1;
  if (st.top - index + 1 < 0)
    printf("Invalid Index \n");
  x = st.S[st.top - index + 1];
  return x;
}

int isEmpty(struct Stack st) {
  if (st.top == -1)
    return 1;
  return 0;
}

int isFull(struct Stack st) {
  return st.top == st.size - 1;
}

int stackTop(struct Stack st) {
  if (!isEmpty(st))
    return st.S[st.top];
  return -1;
}

int isBalance (char *exp){
    struct Stack st;
    st.size = strlen (exp);
    st.top = -1;
    
    st.S = (int * ) malloc(st.size * sizeof(char));
    
    for(int i = 0; exp[i] != '
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Stack {
int size;
int top;
int * S;
};
void create(struct Stack * st) {
printf("Enter Size: ");
scanf("%d", & st -> size);
st -> top = -1;
st -> S = (int * ) malloc(st -> size * sizeof(int));
}
void Display(struct Stack st) {
int i;
for (i = st.top; i >= 0; i--)
printf("%d ", st.S[i]);
printf("\n");
}
void push(struct Stack * st, int x) {
if (st -> top == st -> size - 1)
printf("Stack overflow\n");
else {
st -> top++;
st -> S[st -> top] = x;
}
}
int pop(struct Stack * st) {
int x = -1;
if (st -> top == -1)
printf("Stack Underflow\n");
else {
x = st -> S[st -> top--];
}
return x;
}
int peek(struct Stack st, int index) {
int x = -1;
if (st.top - index + 1 < 0)
printf("Invalid Index \n");
x = st.S[st.top - index + 1];
return x;
}
int isEmpty(struct Stack st) {
if (st.top == -1)
return 1;
return 0;
}
int isFull(struct Stack st) {
return st.top == st.size - 1;
}
int stackTop(struct Stack st) {
if (!isEmpty(st))
return st.S[st.top];
return -1;
}
int isBalance (char *exp){
struct Stack st;
st.size = strlen (exp);
st.top = -1;
st.S = (int * ) malloc(st.size * sizeof(char));
for(int i = 0; exp[i] != '\0'; i++){
if (exp[i] == '(')
push(&st, exp[i]);
else if(exp[i] == ')'){
if(isEmpty(st)) 
return 0;
pop(&st);
}
}
return isEmpty(st)? 1:0;
}
int main() {
char* Exp1 = "((a+b)*(c-d))";
char* Exp2 = "((a+b)*(c-d)))";
if(isBalance(Exp1)) printf("%s has Balanced Parenthesis", Exp1);
else printf("%s has not Balanced Parenthesis", Exp1);
printf("\n");
if(isBalance(Exp2)) printf("%s has Balanced Parenthesis", Exp2);
else printf("%s has not Balanced Parenthesis", Exp2);
return 0;
}
'; i++){
        if (exp[i] == '(')
            push(&st, exp[i]);
        else if(exp[i] == ')'){
            if(isEmpty(st)) 
                return 0;
            pop(&st);
        }
    }
    
    return isEmpty(st)? 1:0;
}

int main() {
  char* Exp1 = "((a+b)*(c-d))";
  char* Exp2 = "((a+b)*(c-d)))";
  
  if(isBalance(Exp1)) printf("%s has Balanced Parenthesis", Exp1);
  else printf("%s has not Balanced Parenthesis", Exp1);
  
  printf("\n");
  
  if(isBalance(Exp2)) printf("%s has Balanced Parenthesis", Exp2);
  else printf("%s has not Balanced Parenthesis", Exp2);

  return 0;
}

Output:

Conclusion:

So, the conclusion is that this procedure doesn’t check whether the parentheses are properly given or not. Instead, it only verifies whether the number of parentheses is matching or not. It checks if for every opening bracket, there is a corresponding closing bracket, thereby ensuring the balancing of parentheses. In the next article, we will write a program for parenthesis checking in the C language.

In the next article, I will discuss Expressions with Balanced Brackets using a Stack in C. In this article, I explain Parenthesis Matching using a Stack in C Language with Examples. I hope you enjoy this article on Parenthesis Matching using a Stack.