reverse polish (postfix) notation parser in C

reverse_polish.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <ctype.h>

typedef enum Type {
	TYPE_NONE     = 1<<0,
	TYPE_OPERATOR = 1<<1,
	TYPE_NUMERIC  = 1<<2,
	TYPE_VARIABLE = 1<<3,
} type_e;

typedef union Value {
	char operator;
	long  numeric;
	char variable;
} value_u;

typedef struct Tree {
	type_e type;
	value_u val;
	struct Tree *left;
	struct Tree *right;
} tree_s;

int
typeof_char(char c) {
	return (
		(ispunct(c)<<1) | (isdigit(c)<<2) | (isalpha(c)<<3)
	);
}

tree_s*
tree_make(type_e type, value_u value, tree_s *left, tree_s *right) {
	tree_s *tree = (tree_s*) calloc(1, sizeof(tree_s));
	tree->type   = type;
	tree->val    = value;
	tree->left   = left;
	tree->right  = right;
	return tree;
}

char*
tree_print(tree_s *tree) {
	if(!tree) return calloc(1, sizeof(char));
	char *left  = tree_print(tree->left);
	char *right = tree_print(tree->right);
	char *value = calloc(8, sizeof(char));
	switch(tree->type) {
		case TYPE_OPERATOR:
			snprintf(value, 8, "%c", tree->val.operator);
			break;
		case TYPE_NUMERIC:
			snprintf(value, 8, "%ld", tree->val.numeric);
			break;
		case TYPE_VARIABLE:
			snprintf(value, 8, "%c", tree->val.variable);
			break;
		default:
			break;
	}
	size_t total = strlen(left) + strlen(value) + strlen(right) + 16;
	char *buffer = (char*) calloc(1+total, sizeof(char));
	snprintf(buffer, total, "]%s>%s<%s[", left, value, right);
	free(left);
	free(right);
	free(value);
	return buffer;
}

void
tree_print_2d(tree_s *tree, int space) {
	static int indent = 4;
	if(!tree) return;
	space += indent;
	tree_print_2d(tree->left, space);
	for(int i=indent; i<space; i++) {
		printf("%c",  (space-indent) > i ? (i%indent ? ' ' : '|') : '.');
	}
	switch(tree->type) {
		case TYPE_OPERATOR:
			printf("%c", tree->val.operator);
			break;
		case TYPE_NUMERIC:
			printf("%ld", tree->val.numeric);
			break;
		case TYPE_VARIABLE:
			printf("%c", tree->val.variable);
			break;
		default:
			break;
	}
	printf("\n");
	tree_print_2d(tree->right, space);
}

void
tree_free(tree_s *tree) {
	if(tree->left) tree_free(tree->left);
	if(tree->right) tree_free(tree->right);
	free(tree);
	return;
}

tree_s*
postfix_parse(const char *expr, tree_s **stack, size_t stack_size) {
	tree_s *current = tree_make(TYPE_NONE, (value_u) { .numeric = 0 }, NULL, NULL);
	while(expr && *expr && isspace(*expr)) expr += 1;
	switch(typeof_char(*expr)) {
		case TYPE_OPERATOR:
			current->type  = TYPE_OPERATOR;
			current->val   = (value_u) { .operator = (*expr) };
			current->left  = stack[stack_size-1];
			current->right = stack[stack_size-2];
			stack_size -= 2;
			stack = (tree_s**) realloc(stack, stack_size * sizeof(tree_s*));
			break;
		case TYPE_NUMERIC:
			current->type = TYPE_NUMERIC;
			current->val.numeric = atol(expr);
			break;
		case TYPE_VARIABLE:
			current->type = TYPE_VARIABLE;
			current->val.operator = *expr;
			break;
		default:
			break;
	}
	stack_size += 1;
	stack = (tree_s**) realloc(stack, stack_size * sizeof(tree_s*));
	stack[stack_size-1] = current;
	while(expr && *expr && !isspace(*expr)) expr += 1;
	if(expr && *expr) return postfix_parse(expr, stack, stack_size);
	return *stack;
}

int
main(int argc, const char **argv) {
	for(int i=1; i<argc; i++) {
		printf("parsing '%s'...\n", argv[i]);
		tree_s *t = postfix_parse(argv[i], NULL, 0);
		char *p = tree_print(t);
		printf("tree: %s\n", p);
		tree_print_2d(t, 0);
		tree_free(t);
		free(p);
		continue;
	}
	return 0;
}

/*
[[>20<]>+<[[[>15<]>*<[>5<]]>+<[>10<]]]


|                                    |
 |                                  |
  >20<|                            |
       >+<|                   |>10<
           |              |>+<
            |            |
             >15<|   |>5<
                  >*<
*/