Application of stack-parentheses checking in an expression

Let us see how we can use stack in problem solving. Consider a mathematical expression which contains a sets of nested parentheses— (x-(a+b) *(x-y)) and we have to check whether the parentheses are nested correctly. Actually we have to check two points.

There are equal numbers of left and right parentheses.

Every right parenthesis is preceded by a matching left parenthesis.

Expression such as ((A+B) violates first condition and expressionsuch as (A+B} * { C+D) violates the second condition.

To solve such problem, we have to design a stack where each opening parentheses ‘(‘ , ‘{‘ or ‘[‘ of the expression will be pushed and when any closing parentheses is encountered , last inserted item from the stack will popped and checked with the closing parentheses. If mismatch is found, the expression is incorrect. At the end of the push and pop operation the stack should be empty to ensure that there are equal number opening and closing parentheses.

# include< stdio.h >

# include< stdlib.h>

int b=0;

struct link

{

char info;

struct link *next;

};

char xxx;

struct link *push(char c,struct link *rec)

{

struct link *new1;

xxx=c;

new1 = (struct link *)malloc(sizeof(struct link));

new1->info=xxx;

new1->next = rec;

rec = new1;

/* Every new opening parentheses is pushed at the top of the stack and pointer rec is made to point the new location */

return rec;

}

struct link * pop(char ch,struct link *rec)

{

struct link *temp;

char xx;

if(rec == NULL)

{

printf("Number of closing parentheses is more than number of closing\n");

b++;

}

else

{

temp=rec->next;

xx=rec->info;

if((xx=='(')&&(ch==')'))

{

free(rec);

rec = temp;

}

else if((xx=='{')&&(ch=='}'))

{

free(rec);

rec = temp;

}

else if((xx=='[')&&(ch==']'))

{

free(rec);

rec = temp;

}

else

{

b++;

}

}

return rec;

}

void main()

{

struct link *start ;

int d;

char ch='a';

clrscr();

start = NULL;

printf("\nEnter the expression:-");

while(ch!='\n')

{

ch=getchar();

if((ch=='(')||(ch=='{')||(ch=='['))

{

start=push(ch,start);

}

if((ch==')')||(ch=='}')||(ch==']'))

{

start=pop(ch,start);

}

if(b!=0)

break;

}

if(b!=0)

// mismatch is found.

printf("Expression is not Correct.");

else if(start==NULL)

/* this indicates that all items from the stack are poped and no mismatch was found. */

printf("Correct Expression.");

else

/* This point indicates that no mismatch is found but still there are items in the stack. So mismatch in number of opening and closing parentheses. */

printf("Expression is not Correct.");

getch();

}