path: root/src/search_stuff.c

#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;
}