 Balanced parentheses using Stack

One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched. Here are some of the balanced and unbalanced expressions. Consider the above mentioned unbalanced expressions,

• The first expression ( a + b is unbalanced as there is no closing parenthesis given.
• The second expression [ ( c - d  * e ] is unbalanced as the closed round parenthesis is not given.
• The third expression { [ ( ] ) } is unbalanced as the nesting of square parenthesis and the round parenthesis are incorrect.

Steps to find whether a given expression is balanced or unbalanced

• Input the expression and put it in a character stack.
• Scan the characters from the expression one by one.
1. If the scanned character is a starting bracket ( ‘ ( ‘ or ‘ { ‘ or ‘ [ ‘), then push it to the stack.
2. If the scanned character is a closing bracket ( ‘ ) ’  or ‘ } ’  or ‘ ] ’ ), then pop from the stack and if the popped character is the equivalent starting bracket, then proceed. Else, the expression is unbalanced.
•  After scanning all the characters from the expression, if there is any parenthesis found in the stack or if the stack is not empty, then the expression is unbalanced.
• Now, let us see a program to check balanced parentheses in the given expression.

C program to check balanced parentheses using stack

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 20

struct stack
{
char stk[MAX];
int top;
}s;

void push(char item)
{
if (s.top == (MAX - 1))
printf ("Stack is Full\n");
else
{
s.top = s.top + 1; // Push the char and increment top
s.stk[s.top] = item;
}}

void pop()
{
if (s.top == - 1)
{
printf ("Stack is Empty\n");
}
else
{
s.top = s.top - 1; // Pop the char and decrement top
}}

int main()
{
char exp[MAX];
int i = 0;
s.top = -1;
printf("\nINPUT THE EXPRESSION : ");
scanf("%s", exp);
for(i = 0;i < strlen(exp);i++)
{
if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
{
push(exp[i]); // Push the open bracket
continue;
}
else if(exp[i] == ')' || exp[i] == ']' || exp[i] == '}') // If a closed bracket is encountered
{
if(exp[i] == ')')
{
if(s.stk[s.top] == '(')
{
pop(); // Pop the stack until closed bracket is found
}
else
{
printf("\nUNBALANCED EXPRESSION\n");
break;
}}
if(exp[i] == ']')
{
if(s.stk[s.top] == '[')
{
pop(); // Pop the stack until closed bracket is found
}
else
{
printf("\nUNBALANCED EXPRESSION\n");
break;
}}
if(exp[i] == '}')
{
if(s.stk[s.top] == '{')
{
pop(); // Pop the stack until closed bracket is found
}
else
{
printf("\nUNBALANCED EXPRESSION\n");
break;
}}}}
if(s.top == -1)
{
printf("\nBALANCED EXPRESSION\n"); // Finally if the stack is empty, display that the expression is balanced
}}

OUTPUT  Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

2    3