-
-
Notifications
You must be signed in to change notification settings - Fork 4.4k
/
parenthesis.c
119 lines (106 loc) · 2.41 KB
/
parenthesis.c
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100
struct node
{
char data;
struct node *link;
};
int c = 0; // c used as counter to check if stack is empty or not
struct node *head; // declaring head pointer globally assigned to NULL
void push(char x) // function for pushing
{
struct node *p = head, *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = x;
if (head ==
NULL) // will be execute only one time i.e, 1st time push is called
{
head = temp;
p = head;
p->link = NULL;
c++;
}
else
{
temp->link = p;
p = temp;
head = p;
c++;
}
}
char pop(void) // function for pop
{
char x;
struct node *p = head;
x = p->data;
head = p->link;
free(p);
c--;
return x;
}
int isBalanced(char *s)
{
int i = 0;
char x;
while (s[i] != '\0') // loop for covering entire string of brackets
{
// printf("\t s[i]=%c\n", s[i]); //DEBUG
if (s[i] == '{' || s[i] == '(' ||
s[i] == '[') // if opening bracket then push
push(s[i]);
else
{
if (c <= 0) // i.e, stack is empty as only opening brackets are
// added to stack
return 0;
x = pop();
if (x == '{' && s[i] != '}')
return 0;
if (x == '[' && s[i] != ']')
return 0;
if (x == '(' && s[i] != ')')
return 0;
}
i++;
}
// at end if stack is empy which means whole process has been performed
// correctly so return 1
return (c == 0) ? 1 : 0;
}
void destroyStack(void)
{
struct node *p = head;
if (c > 0)
{
while (p->link)
{
struct node *tmp = p;
p = p->link;
free(tmp);
}
c = 0;
}
}
int main(void)
{
int t;
printf("\t\tBalanced parenthesis\n\n");
printf("\nPlease enter the number of processing rounds? ");
scanf("%d", &t);
for (int a0 = 0; a0 < t; a0++)
{
char s[SIZE];
printf("\nPlease enter the expression? ");
scanf("%s", s);
if (isBalanced(s))
printf("\nYES\n");
else
printf("\nNO\n");
/* tidy up stack for new round */
destroyStack();
}
return 0;
}