Multiple Parenthesis Match Problem in Stack using ARRAY

amannarayanm · October 13, 2021 · C
#include <stdio.h>
#include <stdlib.h>

struct node {
  int top;
  int size;
  char *arr;
};

int isEmpty(struct node *ptr){
    if(ptr->top == -1){
        return 1;
    }
    else{
        return 0;
    }
}

int isFull(struct node* ptr){
    if(ptr->top == ptr->size-1){
        return 1;
    }
    return 0;
}

void push(struct node* ptr,char ch){
    if(isFull(ptr)){
        printf("\nSTack Overflow!");
    }
    else{
        ptr->top++;
        ptr->arr[ptr->top] = ch;
    }
}

char pop(struct node* ptr){
    if(isEmpty(ptr)){
        printf("\nSTack UnderFlow!");
    }
    else{
        char ch = ptr->arr[ptr->top];
        ptr->top--;
        return ch;
    }
}

char peek(struct node*ptr,int pos){
    int Indarr = ptr->top-pos+1;
    if(Indarr < 0){
        printf("\nNot a Valid Position in Your stack");
    }
    else{
        return ptr->arr[Indarr];
    }
}

int match(char a,char b){
    if(a=='(' && b == ')'){
        return 1;
    }
    if(a=='{' && b== '}'){
        return 1;
    }
    if(a == '[' && b== ']'){
        return 1;
    }
    return 0;
}

int parenthesisMatch(char *Exp){
    
    struct node *sp;
    sp = (struct node*)malloc(sizeof(struct node));
    sp->top = -1;
    sp->size = 50;
    sp->arr = (char *)malloc(sp->size*sizeof(char));
    
    for(int i=0;Exp[i] != '\0';i++){
        if(Exp[i] == '(' || Exp[i] == '{' || Exp[i] == '['){
            push(sp,Exp[i]);
        }
        else if(Exp[i] == ')' || Exp[i] == '}' || Exp[i] == ']'){
            if(isEmpty(sp)){
                return 0;
            }
            char popedChar = pop(sp);
            if(!match(popedChar,Exp[i])){
                return 0;
            }
        }
    }
    if(isEmpty(sp)){
        return 1;
    }
    else{
        return 0;
    }
}

int main() {
    
    char mystr[] = "[(4+5)]+{(5})";
    
    if(parenthesisMatch(mystr)){
        printf("\nBalanced Parenthesis in Expression");
    }
    else{
        printf("\nUnbalanced Parenthesis in Expression");
    }
    
    
    return 0;
}

Comments

Please sign up or log in to contribute to the discussion.