tree.c

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

#define MAX 100
#define SIZE 100
#define newnode() ((struct node *)(calloc(sizeof(struct node), 1)))
#define pop() ((struct node *)(*(--sp)))
#define push(P) ((*(sp++)) = (struct node *)P)

struct node {
  struct node *left, *right;
  char record;
} *stack[SIZE], **sp;

void print_inter(struct node *p)
{
  if(((unsigned long)p->right | (unsigned long)p->left) == NULL) {
    printf("%c", p->record);
  }
  else {
    printf("(");
    print_inter(p->left);
    printf("%c", p->record);
    print_inter(p->right);
    printf(")");
  }
}

void print_prefix(struct node *p)
{
  if(((unsigned long)p->right | (unsigned long)p->left) == NULL) {
    printf("%c", p->record);
  }
  else {
    printf("%c", p->record);
    print_prefix(p->left);
    print_prefix(p->right);
  }
}

void analysis(char *pstr)
{
  struct node *new;

  while(1) {  
    if(*pstr == '\0') { break; }
    switch(*pstr) {
    case '+':
    case '-':
    case '*':
    case '/':
      new = newnode();
      new->record = *pstr;
      new->right = pop();
      new->left = pop();
      push(new);
      break;
    default:
      new = newnode();
      new->record = *pstr;
      /*      new.right = NULL;
	      new.left = NULL;*/
      push(new);
      break;
    }
    
    pstr++;
  }
}

int main(void)
{
  char str[MAX];

  scanf("%s", str);
  str[MAX - 1] = '\0';

  sp = stack;
  analysis(str);
  print_inter(*(sp - 1));
  puts("");
  print_prefix(*(sp - 1));
  puts("");
  
  return 0;
}