/* Boldface = additions to the bare parser. */
/* treerw.c: read and write binary trees
 * grammar:
 *   bintree --->  tree '#'
 *   tree ---> '0' | '(' letter tree tree ')'
 *   letter ---> 'a' | 'b' | 'c' | ...
 */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
char next; /* holds next char read */

void error(int);
void scan(void);
struct tnode *tree(void); /* to build the tree */
void treeprint(struct tnode *); /* to write the tree */

struct tnode { /* typical binary tree node */
   char ch;
   struct tnode *left;
   struct tnode *right;
};

void main(void) {
   struct tnode *root;
   scan();
   root = tree();
   if (next != '#') error(1);
   treeprint(root);
   printf("#\n");
}

struct tnode *tree(void) {
   struct tnode *p ;
   if (next == '0') {
      scan();
      p = NULL;
   }
   else {
      p = (struct tnode *) malloc(sizeof(struct tnode));
      if (next == '(')
         scan();
      else error(2);
      if (isalpha(next)) {
         p -> ch = next;
         scan();
      }
      else error(3);
      p -> left = tree();
      p -> right = tree();
      if (next == ')')
         scan();
      else error(4);
   }
   return p;
}

void scan(void) {
   while (isspace(next = getchar()))
      ;
}

void error(int n) {
   printf("\n*** ERROR: %i\n", n);
   exit(1);
}

/* treeprint: recursive inorder print of tree p */
void treeprint(struct tnode *p)
{
   if (p == NULL) printf("0");
   else {
      /* turn lowercase into uppercase */
      printf("( %c ", (p -> ch) - 32);
      treeprint(p -> left);
      printf(" ");
      treeprint(p -> right);
      printf(" )");
   }
}

ten60% treerw
(a  0  0) #
( A 0 0 )#
ten60% treerw
(a  (b 0 0) (c 0 0) ) #
( A ( B 0 0 ) ( C 0 0 ) )#
ten60% treerw
(a (b (d 0 0) 0) (c (e 0 0) (f 0 0))) #
( A ( B ( D 0 0 ) 0 ) ( C ( E 0 0 ) ( F 0 0 ) ) )#
ten60% treerw
(m (f (a 0 (d 0 0)) (j 0 0)) (t (s (o (n 0 0) 0) 0) (w 0 0)))#
( M ( F ( A 0 ( D 0 0 ) ) ( J 0 0 ) ) ( T ( S ( O ( N 0 0 ) 0 ) 0 ) ( W 0 0 ) ) )#


This last tree is a binary search tree produced by the processing
the following letters in the order shown: mtwfsjaond.


                            m
                           / \
                          /   \
                         /     \
                        /       \
                       /         \
                      /           \
                     f             t
                    / \           / \
                   /   \         /   \
                  a     j       s     w
                 / \   / \     / \   / \
                0   d 0   0   o   0 0   0
                   / \       / \
                  0   0     n   0
                           / \
                          0   0