#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>

typedef enum operator {
  NUMBER,
  PLUS,
  MINUS,
  TIMES,
  AND,
  OR,
  XOR,
  NOT,
  SHL,
  SHR,
} operator_t;

typedef struct elem {
  operator_t op;
  int value;
} elem_t;

// -------- Stack -----------

typedef struct stack {
  size_t max_stack_size;
  size_t stack_size;
  int *items;
} stack_t;

stack_t create_stack(size_t max_stack_size) {
  int *items = (int *) malloc(max_stack_size * sizeof(int));
  stack_t stack = { max_stack_size, 0, items };
  return stack;
}

void free_stack(stack_t *stack) {
  free(stack->items);
}

bool push(stack_t *stack, int elem) {
  if (stack->stack_size < stack->max_stack_size) {
    // On a encore de la place ; on peut empiler l'élément
    stack->items[stack->stack_size] = elem;
    stack->stack_size++;
    return true;
  } else {
    // Il n'y a plus de place ; on ne touche à rien et on renvoie false
    return false;
  }
}

bool pop(stack_t *stack, int *elem) {
  if (stack->stack_size > 0) {
    // Il y a au moins un élément dans la pile
    stack->stack_size--; // ici on décrémente d'abord stack_size
    *elem = stack->items[stack->stack_size];
    return true;
  } else {
    // La pile est vide ; on ne touche à rien et on renvoie false
    return false;
  }
}

// -------- Dynamic array of elem_t -----------

typedef struct elems {
  size_t max_size;
  size_t size;
  elem_t *items;
} elems_t;

elems_t create_elems() {
  // On va doubler la taille plus tard, donc on ne veut jamais 0 (2*0 == 0 !)
  elem_t *items = (elem_t *) malloc(sizeof(elem_t));
  elems_t array = { 1, 0, items };
  return array;
}

void free_elems(elems_t *array) {
  free(array->items);
}

/* Agrandit le tableau interne, sans changer le contenu logique.
 * Utilisé par elems_add quand on n'a plus de place.
 */
void elems_grow(elems_t *array) {
  size_t new_max_size = array->max_size * 2;

  elem_t *new_items = (elem_t *) malloc(new_max_size * sizeof(elem_t));

  // Recopier les éléments existants
  for (size_t i = 0; i < array->size; i++) {
    new_items[i] = array->items[i];
  }

  // Pour être safe, initialiser le reste à "0".
  for (size_t i = array->size; i < new_max_size; i++) {
    new_items[i].op = NUMBER;
    new_items[i].value = 0;
  }

  free(array->items);
  array->max_size = new_max_size;
  array->items = new_items;
  // size ne change pas. On n'a pas touché à la taille logique du tableau.
}

void elems_add(elems_t *array, const elem_t *value) {
  // Agrandir si on n'a plus de place.
  if (array->size == array->max_size)
    elems_grow(array);

  // Stocker le nouvel élément, puis augmenter la taille logique
  array->items[array->size] = *value;
  array->size++;
}

size_t elems_size(const elems_t *array) {
  return array->size;
}

elem_t elems_get(const elems_t *array, size_t index) {
  assert(index < array->size);
  return array->items[index];
}

elem_t elems_last(const elems_t *array) {
  return elems_get(array, elems_size(array) - 1);
}

void elems_set(elems_t *array, size_t index, const elem_t *new_value) {
  assert(index < array->size);
  array->items[index] = *new_value;
}

void elems_shrink(elems_t *array, size_t new_size) {
  assert(new_size <= array->size);
  array->size = new_size;
}

void elems_remove(elems_t *array, size_t index) {
  assert(index < array->size);
  memmove(&array->items[index], &array->items[index + 1],
      (array->size - index - 1) * sizeof(elem_t));
  array->size -= 1;
}

void elems_insert(elems_t *array, size_t index, const elem_t *new_value) {
  assert(index <= array->size);

  // Agrandir si on n'a plus de place.
  if (array->size == array->max_size)
    elems_grow(array);

  // Déplacer les éléments existants
  memmove(&array->items[index + 1], &array->items[index],
      (array->size - index) * sizeof(elem_t));

  // Insérer le nouvel élément
  array->items[index] = *new_value;

  // Et indiquer que le tableau a grandi
  array->size += 1;
}

// -------- New code -----------

int evaluate(const elems_t *elems) {
  size_t size = elems_size(elems);

  stack_t stack = create_stack(size); // we won't need more stack items than elems

  for (size_t i = 0; i < size; i++) {
    const elem_t elem = elems_get(elems, i);
    switch (elem.op) {
      case NUMBER:
        push(&stack, elem.value);
        break;

      case NOT:
        int arg;
        bool poparg = pop(&stack, &arg);
        assert(poparg && "missing operand");
        push(&stack, ~arg);
        break;

      default:
        int x, y;
        bool popy = pop(&stack, &y);
        bool popx = pop(&stack, &x);
        assert(popy && popx && "missing operands");

        switch (elem.op) {
          case PLUS:
            push(&stack, x + y);
            break;
          case MINUS:
            push(&stack, x - y);
            break;
          case TIMES:
            push(&stack, x * y);
            break;
          case AND:
            push(&stack, x & y);
            break;
          case OR:
            push(&stack, x | y);
            break;
          case XOR:
            push(&stack, x ^ y);
            break;
          case SHL:
            push(&stack, (int) (((unsigned int) x) << y));
            break;
          case SHR:
            push(&stack, (int) (((unsigned int) x) >> y));
            break;
          case NUMBER:
          case NOT:
            assert(false);
        }
    }
  }

  int result;
  bool popresult = pop(&stack, &result);
  assert(popresult && "no result");
  int dummy;
  assert(!pop(&stack, &dummy) && "remaining values on the stack");

  free_stack(&stack);

  return result;
}

bool parse_elems(elems_t *result, size_t argc, char *argv[]) {
  for (size_t i = 1; i < argc; i++) {
    char *arg = argv[i];

    elem_t elem = { NUMBER, 0 };

    char single_char = (strlen(arg) == 1) ? arg[0] : '\0';
    switch (single_char) {
      case '+': elem.op = PLUS; break;
      case '-': elem.op = MINUS; break;
      case '*': elem.op = TIMES; break;
      case '&': elem.op = AND; break;
      case '|': elem.op = OR; break;
      case '^': elem.op = XOR; break;
      case '~': elem.op = NOT; break;
      case '<': elem.op = SHL; break;
      case '>': elem.op = SHR; break;
      default: {
        char *end_ptr;
        elem.value = strtol(arg, &end_ptr, 10);
        if (end_ptr == NULL || end_ptr[0] != '\0') {
          // error
          return false;
        }
      }
    }

    elems_add(result, &elem);
  }

  // Success
  return true;
}

/* Skips a well-formed expression ending at the given `index`.
 * Returns `false` if no well-formed expression ends at the given index.
 * If successful, `index` points to the beginning of the skipped expression
 * after the call.
 */
bool skip_well_formed(const elems_t *elems, size_t *index) {
  if (*index == 0) {
    return false;
  } else {
    *index -= 1;
    elem_t elem = elems_get(elems, *index);

    size_t expected_arg_count;
    if (elem.op == NUMBER) {
      expected_arg_count = 0;
    } else if (elem.op == NOT) {
      expected_arg_count = 1;
    } else {
      expected_arg_count = 2;
    }

    // Skip the arguments
    for (size_t i = 0; i < expected_arg_count; i++) {
      if (!skip_well_formed(elems, index)) {
        return false;
      }
    }
    return true;
  }
}

size_t skip_well_formed_direct(const elems_t *elems, size_t index) {
  bool check = skip_well_formed(elems, &index);
  assert(check);
  return index;
}

bool is_well_formed(const elems_t *elems) {
  size_t index = elems_size(elems);
  if (!skip_well_formed(elems, &index)) {
    return false;
  }
  return index == 0;
}

/* Converts the well-formed expression ending at the given `index` to infix.
 *
 * Decreases `end` until the beginning of the converted expression.
 */
char *to_infix_rec(const elems_t *elems, size_t *index) {
  assert(*index > 0);

  *index -= 1;
  elem_t elem = elems_get(elems, *index);

  if (elem.op == NUMBER) {
    // The longest signed 32-bit integer is -2147483648, which contains 11 chars
    char *result = (char *) calloc(11 + 1, sizeof(char));
    sprintf(result, "%d", elem.value);
    return result;
  } else if (elem.op == NOT) {
    char *arg_str = to_infix_rec(elems, index);

    char *result = (char *) calloc(1 + strlen(arg_str) + 1, sizeof(char));
    strcat(result, "~");
    strcat(result, arg_str);

    free(arg_str);
    return result;
  } else {
    char *right_str = to_infix_rec(elems, index);
    char *left_str = to_infix_rec(elems, index);

    char *result = (char *) calloc(5 + strlen(left_str) + strlen(right_str) + 1, sizeof(char));
    strcat(result, "(");
    strcat(result, left_str);
    switch (elem.op) {
      case PLUS:  strcat(result, " + "); break;
      case MINUS: strcat(result, " - "); break;
      case TIMES: strcat(result, " * "); break;
      case AND:   strcat(result, " & "); break;
      case OR:    strcat(result, " | "); break;
      case XOR:   strcat(result, " ^ "); break;
      case SHL:   strcat(result, " < "); break;
      case SHR:   strcat(result, " > "); break;

      case NUMBER:
      case NOT:
        assert(false);
    }
    strcat(result, right_str);
    strcat(result, ")");

    free(left_str);
    free(right_str);
    return result;
  }
}

char *to_infix(const elems_t *elems) {
  size_t index = elems_size(elems);
  return to_infix_rec(elems, &index);
}

bool is_number(const elem_t elem, int value) {
  return elem.op == NUMBER && elem.value == value;
}

/* Computes the log2 of the given value.
 * If `x` is not a power of 2, returns `-1`.
 */
int int_log2(int x) {
  if (x < 1) {
    return -1;
  } else if (x == 1) {
    return 0;
  } else if (x % 2 != 0) {
    return -1;
  } else {
    int log2_x_div_2 = int_log2(x / 2);
    if (log2_x_div_2 == -1) {
      return -1;
    } else {
      return log2_x_div_2 + 1;
    }
  }
}

elems_t simplify(const elems_t *elems) {
  elems_t simplified = create_elems();

  size_t size = elems_size(elems);
  for (size_t i = 0; i < size; i++) {
    elem_t elem = elems_get(elems, i);

    size_t simplified_size = elems_size(&simplified);

    switch (elem.op) {
      case PLUS: {
        elem_t prev = elems_get(&simplified, simplified_size - 1);
        // 0 +  ->  nothing
        if (is_number(prev, 0)) {
          elems_shrink(&simplified, simplified_size - 1);
          continue;
        }

        // 0 ...y +  ->  ...y
        size_t y_begin = skip_well_formed_direct(&simplified, simplified_size);
        assert(y_begin > 0);
        if (is_number(elems_get(&simplified, y_begin - 1), 0)) {
          elems_remove(&simplified, y_begin - 1);
          continue;
        }

        // ...x ~ 1 +  ->  0 ...x -
        if (is_number(prev, 1) && elems_get(&simplified, simplified_size - 2).op == NOT) {
          // drop the 1 and the ~
          elems_shrink(&simplified, simplified_size - 2);
          simplified_size -= 2;

          // insert a 0 before the remaining argument
          size_t x_begin = skip_well_formed_direct(&simplified, simplified_size);
          elem_t zero = { NUMBER, 0 };
          elems_insert(&simplified, x_begin, &zero);

          // add a -
          elem.op = MINUS;
          elems_add(&simplified, &elem);
          continue;
        }

        break;
      }

      case TIMES: {
        // y *  ->  z <  avec z = log2(y) si y est une puissance de 2
        elem_t prev = elems_last(&simplified);
        if (prev.op == NUMBER) {
          int z = int_log2(prev.value);
          if (z != -1) {
            prev.value = z;
            elems_set(&simplified, elems_size(&simplified) - 1, &prev);
            elem.op = SHL;
            elems_add(&simplified, &elem);
            continue;
          }
        }

        break;
      }

      default: {
        // do nothing
      }
    }

    // If we did not 'continue', we did not find a simplification
    elems_add(&simplified, &elem);
  }

  return simplified;
}

int main(int argc, char *argv[]) {
  if (argc <= 1) {
    printf("Passez les éléments en arguments du programmes.\n");
    return 1;
  }

  elems_t elems = create_elems();
  if (!parse_elems(&elems, argc, argv)) {
    printf("Certains éléments sont incorrects.\n");
    free_elems(&elems);
    return 1;
  }

  if (!is_well_formed(&elems)) {
    printf("L'expression n'est pas bien formée.\n");
    free_elems(&elems);
    return 1;
  }

  char *infix_notation = to_infix(&elems);
  printf("Infixe : %s\n", infix_notation);
  free(infix_notation);

  printf("Résultat : %d\n", evaluate(&elems));

  elems_t simplified = simplify(&elems);

  char *simplified_infix = to_infix(&simplified);
  printf("Simplifiée : %s\n", simplified_infix);
  free(simplified_infix);

  printf("Résultat : %d\n", evaluate(&simplified));

  free_elems(&simplified);
  free_elems(&elems);

  return 0;
}