-
Notifications
You must be signed in to change notification settings - Fork 91
/
ma19btech11007_v1.c
149 lines (130 loc) · 3.66 KB
/
ma19btech11007_v1.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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct bst_node {
char str[7] ;
struct bst_node * parent;
struct bst_node * left ;
struct bst_node * right ;
} ;
int compare (char str1[], char str2[]){ // if string 1 is greter, then returns 1
for (int i = 0 ; i<6; i++){ // if string 2 is greater then returns 2
if ((int)str1[i]>(int)str2[i])
return 1 ;
if ((int)str1[i]<(int)str2[i])
return 2 ;
}
return 0 ;
}
struct bst_node * create_node (char str1[]){
struct bst_node * temp ;
temp = (struct bst_node *)malloc(sizeof(struct bst_node)) ;
temp->left = NULL ;
temp->right = NULL;
temp->parent = NULL ;
// strcpy((temp->str),str1) ;
// (temp->str)[6] = '\0' ;
for (int i = 0 ; i<6 ; i++){
(temp->str)[i] = str1[i] ;
}
(temp->str)[6] = '\0' ;
return temp ;
}
struct bst_node * insert_node (char str1[], struct bst_node * Head){
struct bst_node * temp = create_node(str1) ;
if (Head == NULL)
return temp ;
else {
struct bst_node * itr = Head ;
while (1){
if (compare((itr->str),(temp->str)) == 1){
if (itr->left == NULL){
itr->left = temp ;
temp->parent = itr ;
return Head ;
}
else {
itr = itr->left ;
}
}
else {
if (itr->right == NULL){
itr->right = temp ;
temp->parent = itr ;
return Head ;
}
else {
itr = itr->right ;
}
}
}
}
}
int existe (struct bst_node * Head, char str1[]){
struct bst_node * itr = Head ;
while (1){
if (itr == NULL)
return 0 ;
else if (compare((itr->str),str1) == 1){
itr = itr->left ;
}
else if (compare((itr->str),str1) == 2){
itr = itr->right ;
}
else{
return 1 ;
}
}
}
void path_print (struct bst_node * Head, char str1[]){
struct bst_node * itr = Head ;
while (1){
if (itr == NULL)
return ;
else if (compare((itr->str),str1) == 1){
itr = itr->left ;
printf("L") ;
}
else if (compare((itr->str),str1) == 2){
itr = itr->right ;
printf("R") ;
}
else{
return ;
}
}
}
int main(){
struct bst_node * Head = NULL ;
char* firstLine=NULL;
char* inputLine=NULL;
size_t length=0, counter=0, plateLength=6;
char choice, numberPlate[7];
// Fetching only the first line of input.
length = getline(&firstLine,&length,stdin);
// Parsing the string word by word.
while(counter<length){
strncpy(numberPlate,&firstLine[counter],plateLength);
numberPlate[plateLength] = '\0';
counter += plateLength+1; // The +1 takes care of the space between words.
// Call your BST Insert function here with argument: numberPlate
Head = insert_node(numberPlate,Head) ;
}
// Main input handler to serve requests.
while(getline(&inputLine, &length, stdin) != -1){
sscanf(inputLine,"%c %s",&choice, numberPlate);
if(choice=='S'){
// Call your BST Search function here with argument: numberPlate
if (existe(Head,numberPlate) == 0)
printf("0\n") ;
else {
printf("1 ") ;
path_print(Head,numberPlate) ;
printf("\n") ;
}
}
free(inputLine); inputLine=NULL;
length=0;
}
return 0;
}