Balanced parentheses using Stack

05 min read

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.

balanced parentheses

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

balanced expression

unbalanced expression

POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error