DataStructuresProgrammes/ParenthesisMatching.c at master · ayushk128/DataStructuresProgrammes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
struct Stack
{
    int size;
    int top;
    char *arr;
};
int isEmpty(struct Stack *s)
{
    if (s->top == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int isFull(struct Stack *s)
{
    if (s->top == s->size - 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
void push(struct Stack *s, char val)
{
    if (isFull(s))
        printf("\nStack Overflow, Cannot push the %c character.", val);
    else
    {
        s->top++;
        s->arr[s->top] = val;
    }
}
char pop(struct Stack *s)
{
    if (isEmpty(s))
    {
        printf("\nStack Underflow");
        return -1;
    }
    else
    {
        char val = s->arr[s->top];
        s->top--;
        return val;
    }
}
int matched(char a, char b){
    if(a == '{' && b == '}')
        return 1;
    else if(a == '[' && b == ']')
        return 1;
    else if(a == '(' && b == ')')
        return 1;
    else
        return 0;
}
int parenthesisMatched(char *exp){
    struct Stack * sp = (struct Stack*)malloc(sizeof(struct Stack));
    sp->size = 100;
    sp->top = -1;
    sp->arr = (char *)malloc(sp->size*sizeof(char));
    char popped;

    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;
            }
            popped = pop(sp);
            if(!matched(popped, exp[i]))
                return 0;
        }
    }
    if(isEmpty(sp)) return 1;
    else return 0;
}
int main()
{
    char *exp = "{[()]}";
    if(parenthesisMatched(exp))
        printf("\nThe parenthesis is balanced.");
    else
        printf("\nThe parenthesis is not balanced.");
}