alg-06.c

C语言写的

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

#define STACK_SIZE 100

struct node {
  struct node *right;
  char key;
  struct node *left;
};
typedef struct node * NodePointer;

void treeinitialize(void);
NodePointer makenode(char c);
void preorder(NodePointer node);
void inorder(NodePointer node);
void postorder(NodePointer node);
void push(NodePointer x);
NodePointer pop();
int isempty();

NodePointer head, tail;
NodePointer stack[STACK_SIZE];
int stack_count=0;

int main(){
  int c;
  NodePointer node;

  treeinitialize();

  printf("Input data by Reverse Polish Notation: ");
  while( 1 ){
    c = getchar();
    if( c == '\n' ){
      break;
    }

    node=makenode(c);

    if( isdigit((int)node->key) ){
      push( node );
    }else{
      switch( c ){
      case '+':
      case '-':
      case '*':
      case '/':
	node->right=pop();
	node->left=pop();
	push( node );
	break;
      default:
	fprintf(stderr, "input data '%c' is ignored.\n", c);
	/* do nothing */
	break;
      }
    }
  }

  if( stack_count == 1 ){
    head->right=pop();
  }else{
    fprintf(stderr, "Input is invalid\n");
  }

  /* トラバ〖ス */
  printf("preorder:  ");
  preorder(head->right);
  printf("\n");

  printf("inorder:   ");
  inorder(head->right);
  printf("\n");

  printf("postorder: ");
  postorder(head->right);
  printf("\n");

  return 0;
}

void treeinitialize(void){
  head=makenode(-1);
  tail=makenode(-1);
  head->right=tail;
  head->left=tail;
}

/*
 * ノ〖ドを侯喇し、そのノ〖ドへのポインタを手す。
 */
NodePointer makenode(char c){
  NodePointer x;

  x=malloc(sizeof(struct node));
  x->key=c;
  x->right=tail;
  x->left=tail;

  return x;
}

void preorder(NodePointer node){
  if(node!=tail){
    printf("%c ", node->key);
    preorder(node->left);
    preorder(node->right);
  }
}

void inorder(NodePointer node){
  if(node!=tail){
    inorder(node->left);
    printf("%c ", node->key);
    inorder(node->right);
  }
}

void postorder(NodePointer node){
  if(node!=tail){
    postorder(node->left);
    postorder(node->right);
    printf("%c ", node->key);
  }
}

void push(NodePointer x){
  stack[stack_count]=x;
  stack_count++;
}

NodePointer pop(){
  NodePointer ret;

  if( isempty() ){
    fprintf(stderr, "Stack Underflow.\n");
    exit(1);
  }
  stack_count--;
  ret = stack[stack_count];
  return ret;
}

int isempty(){
  if( stack_count==0 ){
    return 1;
  }else{
    return 0;
  }
}