added truth table and expression evaluatorHEADmaster

6 files changed, 163 insertions, 13 deletions

diff --git a/Makefile b/Makefile
index c06e73e..4348395 100644
--- a/Makefile
+++ b/Makefile
@@ -12,7 +12,7 @@ EXES    := $(ARCFIND)
 CFLAGS  := $(addprefix -I,$(SRCDIRS)) $(XTRAFLAGS)
 LDLIBS  :=
 
-ARCFIND_O  := $(addprefix ./bin/, main.o tree.o bu-parser.o)
+ARCFIND_O  := $(addprefix ./bin/, main.o tree.o bu-parser.o truth_table.o)
 
 all: $(EXES)
 .PHONY: all
diff --git a/main.c b/main.c
index 0477bae..a596202 100644
--- a/main.c
+++ b/main.c
@@ -1,11 +1,14 @@
 #include <stdio.h>
+#include <stdint.h>
 #include "tree.h"
 #include "bu-parser.h"
+#include "truth_table.h"
 
 struct lex_str_data {
   const char *str;
   size_t slen;
   size_t needle;
+  uint32_t lttr_bitfield;
 };
 
 struct chartoken lex_str(void *v) {
@@ -17,7 +20,11 @@ struct chartoken lex_str(void *v) {
   do {
   token.c = d->str[d->needle++];
   enum token_id id = TOKEN_INVALID;
-  if (token.c >= 'a' && token.c <= 'z') { token.id = TOKEN_VARIABLE; }
+  if (token.c >= 'a' && token.c <= 'z') {
+    token.id = TOKEN_VARIABLE;
+    int alph_pos = token.c - 'a';
+    d->lttr_bitfield |= 1 << alph_pos;
+  }
   else {
     switch (token.c) {
       case '!': token.id = TOKEN_UNARY_OPERATOR; break;
@@ -36,24 +43,35 @@ int main(){
   char str[100];
   printf("type in your tree(no spaces please): ");
   scanf("%[^\n]", str);
-  char str2[100];
-  strncpy(str2, str, 100);
-  node *exp = parse(str2);
-  printTree(exp,0);
-  free_node(exp);
-
-  struct lex_str_data lxd;
-  lxd.str = str;
-  lxd.slen = strlen(str);
-  lxd.needle = 0;
+
+  struct lex_str_data lxd = {
+    .str = str,
+    .slen = strlen(str),
+    .needle = 0,
+    .lttr_bitfield = 0,
+  };
   struct expr_parser ep = expr_parser_init(lex_str, &lxd);
   enum parser_state s = expr_parser_run(&ep);
   if (s == PARSER_ACCEPT) {
     printTree(ep.stack[0].expr, 0);
   } else {
     expr_parser_debug_print(stderr, &ep);
+    return 1;
   }
+
+  struct truth_table *tt =
+    truth_table_create(ep.stack[0].expr, lxd.lttr_bitfield);
+
+  printf(
+    "%zu : %d : %s\n",
+    tt->letters_count,
+    tt->lines_count,
+    tt->letters
+  );
+
+  truth_table_fprint(stdout, tt);
+
+  truth_table_destroy(tt);
   expr_parser_finish(&ep);
-  
   return 0;
 }
diff --git a/tree.c b/tree.c
index fbb561a..00d5eb9 100644
--- a/tree.c
+++ b/tree.c
@@ -1,5 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdint.h>
 #include "tree.h"
 
 int strichar(const char *str, char c){
@@ -69,3 +70,25 @@ void free_node(node *n) {
   free(n);
 }
 
+char eval_tree(node *root, uint32_t alph_bools) {
+  switch (root->type) {
+    case BIOP: {
+      char lhs = eval_tree(root->lhs, alph_bools);
+      char rhs = eval_tree(root->rhs, alph_bools);
+      switch (root->el) {
+        case '+': return lhs || rhs;
+        case '*': return lhs && rhs;
+        default: fprintf(stderr, "%s: unknown binary operation \"%c\"\n", __func__, root->el);
+      }
+    }
+    case UNOP: {
+      // We only have the not, FIXME if more are added
+      return !eval_tree(root->value, alph_bools);
+    }
+    case LTTR: {
+      char alph_pos = root->el - 'a';
+      return (alph_bools & (1 << alph_pos)) > 0;
+    }
+  }
+}
+
diff --git a/tree.h b/tree.h
index c18ccae..70d2ec0 100644
--- a/tree.h
+++ b/tree.h
@@ -25,4 +25,8 @@ void fprintTree(FILE *stream, node *root, int level);
 void printTree(node *root, int level);
 void free_node(node *n);
 
+/// Takes an expression and a bitfield of the
+/// letters' truthiness values
+char eval_tree(node *root, unsigned int alph_bools);
+
 #endif
diff --git a/truth_table.c b/truth_table.c
new file mode 100644
index 0000000..9ae9463
--- /dev/null
+++ b/truth_table.c
@@ -0,0 +1,77 @@
+#include "truth_table.h"
+
+int intpow(int b, int e) {
+  int acc = 1;
+  for (int i = 0; i < e; i++) {
+    acc *= b;
+  }
+  return acc;
+}
+
+struct expr_input_iter expr_input_iter_init(struct truth_table *tt) {
+  return (struct expr_input_iter){
+    .src = tt,
+    .acc = 0,
+    .count = 0,
+  };
+}
+
+int32_t expr_input_iter_next(struct expr_input_iter *self) {
+  uint32_t bak = self->acc;
+  if (self->count > self->src->lines_count-1) return -1;
+  for (int i = self->src->letters_count - 1; i >= 0; i--) {
+    uint8_t idx = self->src->letters[i] - 'a';
+    self->acc ^= 1 << idx;
+    if (self->acc & (1 << idx)) break;
+  }
+  self->count++;
+  return bak;
+}
+
+struct truth_table *truth_table_create(node *root, uint32_t letters_bitfield) {
+  struct truth_table *tt = calloc(1, sizeof(struct truth_table));
+  char letters[27] = {0};
+  char letters_needle = 0;
+  for (char i = 0; i <= ('z'-'a'); i++) {
+    if (letters_bitfield & (1 << i)) {
+      letters[letters_needle] = 'a'+i;
+      letters_needle++;
+    }
+  }
+  tt->letters = malloc(letters_needle * sizeof(char));
+  strncpy(tt->letters, letters, letters_needle);
+  tt->letters_count = letters_needle;
+  tt->lines_count = intpow(2,tt->letters_count);
+  tt->lines = malloc(tt->lines_count * sizeof(uint32_t));
+
+  struct expr_input_iter inp_iter = expr_input_iter_init(tt);
+  for (int i = 0; i < tt->lines_count; i++) {
+    int32_t input = expr_input_iter_next(&inp_iter);
+    uint8_t output = eval_tree(root, input);
+    tt->lines[i] = input | (output << 26);
+  }
+
+  return tt;
+}
+
+void truth_table_destroy(struct truth_table *tt) {
+  free(tt->lines);
+  free(tt->letters);
+  free(tt);
+}
+
+void truth_table_fprint(FILE *stream, struct truth_table *tt) {
+  fprintf(stream, "\t%s | S\n\t", tt->letters);
+  for (int i = 0; i < (tt->letters_count + 4); i++) putc('-', stream);
+  putc('\n', stream);
+  for (int i = 0; i < tt->lines_count; i++) {
+    putc('\t', stream);
+    uint32_t line = tt->lines[i];
+    for (int j = 0; j < tt->letters_count; j++) {
+      int actual_idx = tt->letters[j] - 'a';
+      putc((line & (1 << actual_idx))? '1' : '0', stream);
+    }
+    fprintf(stream, " | %c\n", (line & (1 << 26))? '1' : '0');
+  }
+}
+
diff --git a/truth_table.h b/truth_table.h
new file mode 100644
index 0000000..37e535a
--- /dev/null
+++ b/truth_table.h
@@ -0,0 +1,28 @@
+#ifndef TRUTH_TABLE_HG_
+#define TRUTH_TABLE_HG_
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include "tree.h"
+
+struct truth_table {
+  uint32_t *lines;
+  uint8_t lines_count;
+  char *letters;
+  size_t letters_count;
+};
+
+struct expr_input_iter {
+  struct truth_table *src;
+  uint32_t acc;
+  uint32_t count;
+};
+
+struct expr_input_iter expr_input_iter_init(struct truth_table *tt);
+int32_t expr_input_iter_next(struct expr_input_iter *self);
+
+struct truth_table *truth_table_create(node *root, uint32_t letters_bitfield);
+void truth_table_destroy(struct truth_table *tt);
+void truth_table_fprint(FILE *stream, struct truth_table *tt);
+
+#endif // TRUTH_TABLE_HG_