Write a C Program to Check Whether Balanced Parentheses or Not Using Linked List

by

Aim:

To write a C Program to Check Whether Balanced Parentheses or Not Using Linked List implementation of a Stack.

Theory:

Description:

  • Compilers check your programs for syntax errors, but frequently a lack of one symbol will cause the compiler to spill out a hundred lines of diagnostics without identifying the real error.
  • Thus, every right brace, bracket and parentheses must correspond to its left counterpart.
  • This can be verified using a stack.

Algorithm:

  1. Make an empty stack implemented as a linked list.
  2. Scan the expression from left to right, character by character.
  3. During your scanning:
    • If you find left parentheses push them into the stack.
    • If you find the right parentheses examine the status of the stack:
      • If the stack is empty then the right parentheses do not have matching left parentheses. So stop scanning and print expression is invalid.
      • If the stack is not empty, pop the stack and continue scanning.
  4. When the end of the expression is reached, the stack must be empty. Otherwise one or more left parentheses has been opened and not closed.

Program:

#include<stdio.h>
#include<stdlib.h>
struct stack
{
char data;
struct stack* next; 	
}*top=NULL,*newnode;
struct stack* temp; 
void push(char k)
{	
newnode=(struct stack*)malloc(sizeof(struct stack));	
if(top==NULL)	
{
newnode->data=k;
top=newnode;
top->next=0;
}
else
{
newnode->data=k;
newnode->next=top;
top=newnode;
}	
}
int pop()
{   
if(top==NULL)
{
printf("EXPRESSION UNBALANCED");
return 1;
}
else
{
temp=top;
top=top->next;
temp->next=NULL;
return 0;	
}
}
int main()
{
char str[100];
int check1=0,i;
printf("ENTER THE EXPERSION\n");
scanf("%s",str);
for( i=0;str[i]!='\0';i++)
{
if(str[i]=='{'||str[i]=='('||str[i]=='[')
{
push(str[i]);
}
else if(str[i]=='}'||str[i]==')'||str[i]==']')
{
check1=pop();
}
if(check1==1)
{
return 0;
}
}
if(top==NULL)
{
printf("EXPERSION IS BALANCED");
}
else
{
printf("EXPRESSION IS UNBALANLCED");
}
return 0;
}

Execution:

Input:
{[]}{()}


Output:
INPUT THE EXPRESSION : {[]}{()} 
BALANCED EXPRESSION

Result:

Thus, Implement of Balanced parentheses or not using linked list implementation of a stack was executed successfully.

Leave a Comment