Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
Name : Aastha dubey Class/Roll No :D6ADA/14 Grade :
EXPERIMENT
– 03
Aim :- Write a program for parenthesis matching using stack.
Theory :-
➔ Parenthesis matching is a process in which we verify if opening and
closing of parentheses are correctly [Link] ensures that all the
parentheses are perfectly paired with each other's counterparts.
➔ It ensures that there's no mismatch in parenthesis and equal pairing
is done.
It is very important for code to have parenthesis matching as it ensures proper
functioning of code and prevents misinterpretations.
❖ Algorithm for parenthesis matching
:- Step 1:- Empty stack initialisation
Step 2:- Read the input expression
Step 3:-
➢ If it's an opening parenthesis ('(', '{', '['), push it onto the stack.
➢ If it's a closing parenthesis (')', '}', ']'):
● if the stack is empty return " unmatched parenthesis.
● if pop the element from top of the stack.
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
● after the process if stack is empty return" matches
parenthesis".
● otherwise return"unmatched parenthesis".
Code :-
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 30
int top=-1;
int stack[MAX];
void push(char);
char pop();
int match(char a,char b);
int check(char []);
int main()
{
char exp[MAX];
int valid;
printf("Enter an algebraic expression : ");
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
gets(exp);
valid=check(exp);
if(valid==1)
printf("\nMatched Parenthesis");
else
printf("\nUnmatched Parenthesis");
return 0;
}
int check(char exp[] )
{
int i;
char temp;
for(i=0;i<strlen(exp);i++)
{
if(exp[i]=='(' || exp[i]=='{' || exp[i]=='[')
push(exp[i]);
if(exp[i]==')' || exp[i]=='}' || exp[i]==']')
if(top==-1)
{
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
printf("\nRight parentheses are more than left parentheses");
return 0;
}
else
{
temp=pop();
if(!match(temp, exp[i]))
{
printf("\nMismatched parentheses are : ");
printf("%c and %c\n",temp,exp[i]);
return 0;
}
}
}
if(top==-1)
{
printf("\nBalanced
P
ar
}
en
else
th
{
es
es
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
");
re
tu
rn
1;
printf("\nLeft parentheses more than
right parentheses");
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
return 0;
}
}
int match(char a,char b)
{
if(a=='[' && b==']')
return 1;
if(a=='{' && b=='}')
return 1;
if(a=='(' && b==')')
return 1;
return 0;
void push(char item)
{
if(top==(MAX-1))
{
printf("\nStack Overflow!!!");
return;
}
top=top+1;
stack[top]=item;
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
}
char pop()
{
if(top==-1)
{
printf("\nStack Underflow!!!");
exit(1);
}
return(stack[top--]);
}
Output :-
D6ADA-Aditya Paranjpe-43
Artificial Intelligence and Data Science Department
DS/Odd Sem 2023-23/Experiment 3
Conclusion :-
● Parenthesis matching acts crucial for data structures
● It tends to ensure proper functioning of code; minimalistic
errors also increase the accuracy .
● It is fundamental for maintaining credibility of any code.
D6ADA-Aditya Paranjpe-43