diff options
| -rw-r--r-- | 21.c | 215 | ||||
| -rw-r--r-- | makefile | 1 |
2 files changed, 216 insertions, 0 deletions
@@ -0,0 +1,215 @@ + +//#define _GNU_SOURCE + +#include <regex.h> +#include <search.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + + +#define arrlen(x) (sizeof(x)/sizeof((x)[0])) + + +enum operation { + OP_VAL, + OP_ADD, + OP_SUB, + OP_MUL, + OP_DIV, +}; + + +enum operation +operation_get(char op) +{ + switch (op) { + case '+': return OP_ADD; + case '-': return OP_SUB; + case '*': return OP_MUL; + case '/': return OP_DIV; + } + return OP_VAL; +} + + +struct monkey { + char name[5]; + enum operation op; + long value; + char left[5]; + char right[5]; +}; + + +struct monkey * +monkey_create_val(char const * name, long value) +{ + struct monkey * m; + + if (!name || strlen(name) != 4) + return NULL; + + if ((m = malloc(sizeof(struct monkey))) == NULL) + return NULL; + + snprintf(m->name, sizeof(m->name), "%s", name); + m->op = OP_VAL; + m->value = value; + m->left[0] = '\0'; + m->right[0] = '\0'; + return m; +} + + +struct monkey * +monkey_create_op(char const * name, enum operation op, char const * left, char const * right) +{ + struct monkey * m; + + if (!name || strlen(name) != 4 + || op == OP_VAL + || !left || strlen(left) != 4 + || !right || strlen(right) != 4) + return NULL; + + if ((m = malloc(sizeof(struct monkey))) == NULL) + return NULL; + + snprintf(m->name, sizeof(m->name), "%s", name); + m->op = op; + m->value = 0; + snprintf(m->left, sizeof(m->left), "%s", left); + snprintf(m->right, sizeof(m->right), "%s", right); + return m; +} + + +int +monkey_cmp(struct monkey const * a, struct monkey const * b) +{ + return strcmp(a->name, b->name); +} + + +int +monkey_cmp_t(void const * a, void const * b) +{ + return monkey_cmp(a, b); +} + + +struct monkey * +monkey_find(void * monkey_tree, char const * name) +{ + struct monkey tmp, ** result; + + if (!name || strlen(name) != 4) { + fprintf(stderr, "Invalid monkey name %s\n", name ? name : "(null)"); + return NULL; + } + + snprintf(tmp.name, sizeof(tmp.name), "%s", name); + result = tfind(&tmp, &monkey_tree, monkey_cmp_t); + return result ? *result : NULL; +} + + +long +monkey_value(void * monkey_tree, struct monkey * m) +{ + long v; + + if (!m) { + fprintf(stderr, "%s: Bad monkey\n", __FUNCTION__); + return 0; + } + + switch (m->op) { + case OP_VAL: + v = m->value; + break; + + case OP_ADD: + v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left)) + + monkey_value(monkey_tree, monkey_find(monkey_tree, m->right)); + break; + + case OP_SUB: + v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left)) + - monkey_value(monkey_tree, monkey_find(monkey_tree, m->right)); + break; + + case OP_MUL: + v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left)) + * monkey_value(monkey_tree, monkey_find(monkey_tree, m->right)); + break; + + case OP_DIV: + v = monkey_value(monkey_tree, monkey_find(monkey_tree, m->left)) + / monkey_value(monkey_tree, monkey_find(monkey_tree, m->right)); + break; + + default: + fprintf(stderr, "Unexpected operation for %s: %d\n", m->name, m->op); + return 0; + } + + return v; +} + + +int +main() +{ + regex_t reval, reop; + char buf[BUFSIZ]; + void * monkey_tree = NULL; + + if (regcomp(&reval, "([[:alpha:]]{4}): (-?[[:digit:]]+)", REG_EXTENDED) != 0 + || regcomp(&reop, "([[:alpha:]]{4}): ([[:alpha:]]{4}) ([-+*/]) ([[:alpha:]]{4})", REG_EXTENDED) != 0) + { + fprintf(stderr, "Bad regex\n"); + return -1; + } + + while (fgets(buf, sizeof(buf), stdin)) { + regmatch_t matches[5]; + struct monkey * m; + + if (regexec(&reval, buf, arrlen(matches), matches, 0) == 0) { + buf[matches[1].rm_eo] = '\0'; + m = monkey_create_val(buf + matches[1].rm_so, atoi(buf + matches[2].rm_so)); + } + else if (regexec(&reop, buf, arrlen(matches), matches, 0) == 0) { + buf[matches[1].rm_eo] = '\0'; + buf[matches[2].rm_eo] = '\0'; + buf[matches[4].rm_eo] = '\0'; + m = monkey_create_op(buf + matches[1].rm_so, + operation_get(buf[matches[3].rm_so]), + buf + matches[2].rm_so, + buf + matches[4].rm_so); + } + else { + fprintf(stderr, "Bad monkey: %s\n", buf); + regfree(&reop); + regfree(&reval); + return -1; + } + + tsearch(m, &monkey_tree, monkey_cmp_t); + } + + + + printf("root value: %ld\n", monkey_value(monkey_tree, monkey_find(monkey_tree, "root"))); + +#ifdef _GNU_SOURCE + tdestroy(monkey_tree, free); +#endif + regfree(&reop); + regfree(&reval); + + return 0; +} + @@ -22,6 +22,7 @@ all: bin \ bin/18 \ bin/19 \ bin/20 \ + bin/21 \ bin: mkdir -p $@ |