1 files changed, 126 insertions, 0 deletions
diff --git a/src/search_stuff.c b/src/search_stuff.c
new file mode 100644
index 0000000..5d4cb6c
--- /dev/null
+++ b/src/search_stuff.c
@@ -0,0 +1,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;
+}