binary tree ( http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001 )

bt.c

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

#ifndef ungetchar
#define ungetchar(c) ungetc((c), stdin)
#endif

typedef struct tree Tree;

struct tree
{
    Tree *left;
    Tree *right;
};

typedef Tree *(*TreeOperator)(Tree *, Tree *);

// almost all function calls exit(1) if allocation failed

Tree *tree_alloc(Tree *left, Tree *right)
{
    Tree *tree = malloc(sizeof(Tree));
  
    if (tree == NULL)
    {
        fprintf(stderr, "tree_alloc failed\n");
        exit(1);
    }
    
    tree->left = left;
    tree->right = right;
  
    return tree;
}

Tree *tree_copy(Tree *tree)
{
    if (tree == NULL) { return NULL; }

    return tree_alloc(tree_copy(tree->left), tree_copy(tree->right));
}

void tree_free(Tree *tree)
{
    if (tree == NULL) { return; }

    tree_free(tree->left);
    tree_free(tree->right);
    free(tree);
}

void tree_print(Tree *tree)
{
    if (tree == NULL) { return; }

    putchar('(');
    tree_print(tree->left);
    putchar(',');
    tree_print(tree->right);
    putchar(')');
}

int get_nonspace_char(void)
{
    int c = getchar();
    
    while (isspace(c))
    {
        c = getchar();
    }
    
    return c;
}

Tree *tree_read(void)
{
    Tree *left;
    Tree *right;
    Tree *tree;
    int c;
    
    c = get_nonspace_char();
    
    if (c != '(')
    {
        ungetchar(c);
        return NULL;
    }
    
    left = tree_read();
    
    c = get_nonspace_char();
    
    if (c != ',')
    {
        ungetchar(c);
        tree_free(left);
        return NULL;
    }
  
    right = tree_read();
    
    c = get_nonspace_char();
    
    if (c != ')')
    {
        ungetchar(c);
        tree_free(left);
        tree_free(right);
        return NULL;
    }
  
    return tree_alloc(left, right);
}

Tree *tree_intersect(Tree *a, Tree *b)
{
    if (a == NULL || b == NULL) { return NULL; }
    
    return tree_alloc(
        tree_intersect(a->left, b->left),
        tree_intersect(a->right, b->right));
}

Tree *tree_union(Tree *a, Tree *b)
{
    if (a == NULL) { return tree_copy(b); }
    if (b == NULL) { return tree_copy(a); }
    
    return tree_alloc(
        tree_union(a->left, b->left),
        tree_union(a->right, b->right));
}

TreeOperator read_tree_operator(void)
{
    int c = get_nonspace_char();
    
    if (c == 'i')
    {
        return tree_intersect;
    }
    
    if (c == 'u')
    {
        return tree_union;
    }
    
    if (c != EOF)
    {
        fprintf(stderr, "read_tree_operator: unexpected char '%c'\n", c);
        exit(1);
    }
    
    return NULL;
}

int main(void)
{
    while (!feof(stdin))
    {
        TreeOperator op = read_tree_operator();
        
        if (op != NULL)
        {
            Tree *a = tree_read();
            Tree *b = tree_read();
            Tree *result = op(a, b);
            
            tree_print(result);
            puts("");
            
            tree_free(a);
            tree_free(b);
            tree_free(result);
        }
    }
    
    return 0;
}