blob: 5d4cb6c24f582f73f474749ea480265fce1d9b4d (
plain) (
blame)
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
|
#include "util.h"
#include "search.h"
char stk[4048];
int p = 0;
/*
* expr : (expr) | expr op expr | not expr | term
* op : and | or
* term : <string>
*
*/
void
reverse_str(char ** s)
{
int l = strlen(*s);
char * rev_s = strdup(*s);
int j = 0;
for (int i = l - 1; i >= 0; i--, j++) {
rev_s[j] = (*s)[i];
}
rev_s[j] = '\0';
free(*s);
*s = rev_s;
}
/*
* Implementing https://www.javatpoint.com/convert-infix-to-prefix-notation
*
* ascii values:
* & -> 38
* | -> 124
* ( -> 40
* ) -> 41
* a-z -> 97-122
* A-Z -> 64-90
*
* precidence:
* & > |
* (http://www.cs.ucc.ie/~gavin/cs1001/Notes/chap40/ch40_16.html)
*/
int
precedence(char c)
{
switch (c) {
case '&':
return 100;
case '|':
return 50;
default:
return 0;
}
}
void
infix_to_prefix(char ** s)
{
char * prefixed = malloc(sizeof(char) * strlen(*s) * 2);
prefixed[0] = '\0';
char * rev_s = strdup(*s);
reverse_str(&rev_s);
for (int i = 0; i < strlen(rev_s); i++) {
if (rev_s[i] == '&' ||
rev_s[i] == '|') {
if (p == 0) {
stk[p++] = rev_s[i];
} else {
if (precedence(rev_s[i] > precedence(stk[p - 1]))) {
stk[p++] = rev_s[i];
} else {
int k = strlen(prefixed);
for (int j = p; j > 0 || precedence(rev_s[i]) < precedence(stk[p - 1]); j--) {
prefixed[k++] = stk[j - 1];
p--;
}
prefixed[k] = '\0';
stk[p++] = rev_s[i];
}
}
}
else if (rev_s[i] == '(') {
stk[p++] = rev_s[i];
}
else if (rev_s[i] == ')') {
int k = strlen(prefixed);
prefixed[k++] = rev_s[i];
for (int j = p; j > 0 && stk[j] != ')'; j--) {
prefixed[k++] = stk[j - 1];
p--;
}
prefixed[k] = '\0';
}
else {
int k = strlen(prefixed);
prefixed[k] = rev_s[i];
prefixed[k+1] = '\0';
}
}
int k = strlen(prefixed);
prefixed[k++] = ' '; // add space after the first operator
for (int j = p; j > 0; j--) {
prefixed[k++] = stk[j - 1];
p--;
}
prefixed[k] = '\0';
printf("rev %s\n", prefixed);
for (int i = 0; i < strlen(prefixed); i++) {
if (prefixed[i] == '(' &&
i < strlen(prefixed) &&
(prefixed[i+1] == '&' || prefixed[i+1] == '|')) {
prefixed[i] = prefixed[i+1];
prefixed[i+1] = '(';
}
}
printf("rev fixed %s\n", prefixed);
reverse_str(&prefixed);
free(rev_s);
free(*s);
*s = prefixed;
}
|
