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

struct Tree {
  int data ;
  struct Tree* left ;
  struct Tree* right ;
} ;

struct Tree* tree_int( int x ) // 数値のノード
{ struct Tree* n ;
  n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
  if ( n != NULL ) {
    n->data = x ;
    n->left = n->right = NULL ;
  }
  return n ;
}

struct Tree* tree_op( int op , // 演算子のノード
		      struct Tree* l , struct Tree* r ) {
  struct Tree* n ;
  n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
  if ( n != NULL ) {
    n->data = op ;
    n->left = l ;
    n->right = r ;
  }
  return n ;
}

// 与えられた演算子の木を計算する関数
int eval( struct Tree* p ) {
  if ( p->left == NULL && p->right == NULL ) {
    // 数値のノードは値を返す
    return p->data ;
  } else {
    // 演算子のノードは、左辺値,右辺値を求め
    // その計算結果を返す
    switch( p->data ) {
    case '+' : return eval( p->left ) + eval( p->right ) ;
    case '*' : return eval( p->left ) * eval( p->right ) ;
    }
  }
}

// 与えられた式を表示
void print_tree( struct Tree* p ) {
  if ( p->left == NULL && p->right == NULL ) {
    printf( "%d" , p->data ) ;
  } else {
    printf( "(") ;
    print_tree( p->left ) ;
    printf( "%c" , p->data ) ;
    print_tree( p->right ) ;
    printf( ")") ;
  }
}

int main() {
  struct Tree* exp = // 1+(2*3) の構文木を生成
    tree_op( '+' ,
	     tree_int( 1 ) ,
	     tree_op( '*' ,
		      tree_int( 2 ) ,
		      tree_int( 3 ) ) ) ;
  // 式を表示
  print_tree( exp ) ;
  // 結果を表示
  printf( " = %d\n" , eval( exp ) ) ;
  return 0 ;
}