From 5a2f6687f681fa0ceff19a42ec9ddce479e67c48 Mon Sep 17 00:00:00 2001 From: Pedro Souza Date: Thu, 4 Apr 2024 01:52:22 -0300 Subject: added truth table and expression evaluator --- Makefile | 2 +- main.c | 42 ++++++++++++++++++++++---------- tree.c | 23 ++++++++++++++++++ tree.h | 4 ++++ truth_table.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ truth_table.h | 28 ++++++++++++++++++++++ 6 files changed, 163 insertions(+), 13 deletions(-) create mode 100644 truth_table.c create mode 100644 truth_table.h 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 +#include #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 #include +#include #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 +#include +#include +#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_ -- cgit v1.2.3