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