Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

C program to check the balance of parenthesis

Balanced Parenthesis

To check balanced parenthesis is a basic interview question where we are asked to find whether the given string(of brackets) is balanced or not. To do this , the traditional way of doing is using stacks (implemented using array). Different brackets are  ( ) , [ ] , { }. Question can be asked on any type of bracket or of all types of brackets.

Example :

  • Sample input: ()(())
  • Sample output: BALANACED STRING
C program to check balanced parenthesis

Algorithm :

  • Declare a structure for character stack.
  • Now traverse the expression string exp. 
    1. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
    2. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else brackets are not balanced.
  • After complete traversal, if there is some starting bracket left in stack then “NOT BALANCED”

C code based on above algorithm :

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

#define MAX 100

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

void push (char item)
{
if (s.top == (MAX - 1))
printf ("Stack is Full\n");

else
{
s.top = s.top + 1;
s.stk[s.top] = item;

}

}

void pop ()
{
if (s.top == -1)
printf ("Stack is Empty\n");

else
s.top = s.top - 1;
}

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]);
continue;

}

else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}')
{

if (exp[i] == ')')
{

if (s.stk[s.top] == '(')
pop ();

else
{

printf ("\nUNBALANCED EXPRESSION\n");
break;

}

}

if (exp[i] == ']')
{

if (s.stk[s.top] == '[')
pop ();

else
{

printf ("\nUNBALANCED EXPRESSION\n");
break;

}

}

if (exp[i] == '}')
{

if (s.stk[s.top] == '{')
pop ();

else
{

printf ("\nUNBALANCED EXPRESSION\n");
break;

}

}

}

}

if (s.top == -1)
printf ("\nBALANCED EXPRESSION\n");

}

Output :

INPUT THE STRING : ()(){{}}

BALANCED EXPRESSION