Question

Problem Implement (in C) an algorithm that uses a stack to check if a parentheses sequence is balanced. Note that a parentheses sequence is balanced if it is of the form (S) or of the form (SS), where S is any balanced parentheses sequence. See the courseware for more information on balanced parentheses sequences. Implement a stack using an array Test your program on three different kinds of inputs: 1. String is unbalanced in the sense that there are more opening (resp. closing) than closing (resp. opening) parentheses. For example: "(()". 2. String has an equal number of opening and closing parentheses but not balanced. That is there exists a closing parenthesis for which there is no nearest opening parenthesis to its left For example "))((". 3. String is balanced and is of the type (S) or of the type SS. For example, ")", or "(())" You must comment your program carefully to enhance its readability and clarity. If your program is not commented you will lose 1 mark.

Answer 1

#include<stdio.h>
#include<string.h>
#define MAX 20

int top = -1;
int stack[MAX];

char push(char item)
{
        if(top == (MAX-1))
                printf("Stack Overflow\n");
        else
        {
                top=top+1;
                stack[top] = item;
        }
}

char pop()
{
        if(top == -1)
                printf("Stack Underflow\n");
        else
                return(stack[top--]);
}


void main()
{
        
        char gp[MAX],t;
        int i,c=1;
        
        printf("Enter an Expression : ");
        gets(gp);
        
        for(i=0;i<strlen(gp);i++)
        {
                if(gp[i]=='(' || gp[i]=='{' || gp[i]=='[')
                        push( gp[i] );
                if(gp[i]==')' || gp[i]=='}' || gp[i]==']')
                        if(top == -1)
                                c=0;
                        else
                        {
                                t=pop();
                                if( gp[i]==')' && (t=='{' || t=='[') )
                                        c=0;
                                if( gp[i]=='}' && (t=='(' || t=='[') )
                                        c=0;
                                if( gp[i]==']' && (t=='(' || t=='{') )
                                        c=0;
                        }
        }
        
        if(top>=0)
                c=0;

        if( c==1)
                printf("This is Valid Expression\n");

        else
                printf("This is Invalid Expression\n");
                
}