C program for implementing balanced parentheses using Stack ADT using array explained, How to implement stack ADT using array for balanced parentheses? How to implement stack data structure using linear array in C?
Implementation of balanced parentheses using stack with array
/* This program
implements balanced parentheses using stack with array. It handles [], (), and {}
brackets. In the input string, if the brackets are not balanced, then the
program shows “Unbalanced” otherwise shows “Balanced” as result.
Working
The program scans the
input string from left to right character by character. If the scanned
character is opening bracket, then inserts the character on to the stack. If the
scanned character is closing symbol ( ‘)’, ‘]’, ‘}’ ), then the program pops
the top element. */
#include <stdio.h>
#include <conio.h>
#define max 50 //to
declare a constant variable (a macro) with a value
int main()
{
char stk[max],exp[100];
int top,i; //declares a variable top to point
to the top element of stack
top = -1; //initialize the top of stack with
-1, that is, empty stack.
printf("\nEnter an infix
expression ");
gets(exp);
for(i=0; exp[i] != '\0'; i++) //’\0’ used to represent NULL
{
//checks whether the
input character is any of the opening symbol
if( exp[i]=='(' || exp[i] =='[' ||
exp[i] == '{' )
{
top++; //if
the input is opening bracket, then top is incremented to 1
stk[top]= exp[i]; //pushes the opening bracket into stack
}
else
if ( exp[i] == ')' ) //if the input is ), then we check for the top element
{
if( stk[top] == '(' ) //if the top of stack is (, then pop the top element
{
top--; //pop
is achieved by decrementing the top variable value
}
else
{
printf("Unbalanced exp"); //if top element is other than (, then print this
getch();
exit(0); //in
case of unbalanced, terminate the program
}
}
else
if ( exp[i] == ']' ) //the above stated thing is checked for ] square bracket
{
if( stk[top] == '[' )
top--;
else
{
printf("Unbalanced exp");
getch();
exit(0);
}
}
else
if ( exp[i] == '}' ) //the above stated thing is checked for } curly brace
{
if( stk[top] == '{' )
top--;
else
{
printf("Unbalanced exp");
getch();
exit(0);
}
}
} // for
if( top == -1 )
printf("Exp is balanced");
else
printf("Exp is not
balanced");
getch();
} // main
***************