fork download
copy 
  1. /* tree syntax parser and display program */
  2. /*
  3.         tree := digit digits ( tree ) ( tree ) | * | <null>
  4.         digit := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  5.         digits := digit digits | <null>
  6. */
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <ctype.h>
  12. typedef struct tree tree;
  13. typedef struct tree {
  14.     unsigned int id;
  15.     tree *left, *right;
  16. } tree;
  17. typedef struct {
  18.     unsigned int width, height, pos;
  19.     char grid[1];
  20. } ascii_t;
  21. int match( const char **s, char c ) {
  22.     if ( s == 0 || *s == 0 || **s != c ) return 0;
  23.     return ++*s, 1;
  24. }
  25. int digit( const char **s ) {
  26.     return match( s, '0' ) || match( s, '1' ) || match( s, '2' ) ||
  27.         match( s, '3' ) || match( s, '4' ) || match( s, '5' ) ||
  28.         match( s, '6' ) || match( s, '7' ) || match( s, '8' ) ||
  29.         match( s, '9' );
  30. }
  31. tree * create( const char **s ) {
  32.     char c;
  33.     unsigned int value;
  34.     tree *node, *left, *right;
  35.     if ( s == 0 || *s == 0 ) return 0;
  36.     if ( match( s, '*' ) ) return 0;
  37.     if ( c= **s, !digit( s ) ) return 0;
  38.     for ( value= c - '0'; c= **s, digit( s ); ) value= 10*value + c - '0';
  39.     if ( !match( s, '(' ) ) return 0;
  40.     left= create( s );
  41.     if ( !match( s, ')' ) || !match( s, '(' ) ) return 0;
  42.     right= create( s );
  43.     if ( !match( s, ')' ) ) return 0;
  44.     node= (tree *) malloc( sizeof( tree ) );
  45.     node->id= value;
  46.     node->left= left;
  47.     node->right= right;
  48.     return node;
  49. }
  50. void destroy( tree * t ) {
  51.     if ( t == 0 ) return;
  52.     destroy( t->left );
  53.     destroy( t->right );
  54.     free( t );
  55.     return;
  56. }
  57. void display( ascii_t *r ) {
  58.     unsigned int i, j;
  59.         for ( i= 0; i < r->height; ++i ) {
  60.             for ( j= 0; j < r->width; ++j )
  61.                 putchar( r->grid[ i*r->width+j ] );
  62.             putchar( '\n' );
  63.         }
  64.     return;
  65. }
  66. void sidedisplay( ascii_t *r ) {
  67.     unsigned int i, j;
  68.         for ( j= 0; j < r->width; ++j ) {
  69.             for ( i= 0; i < r->height; ++i )
  70.                 putchar( r->grid[ i*r->width+j ] );
  71.             putchar( '\n' );
  72.         }
  73.     return;
  74. }
  75. ascii_t * ascii( tree *t ) {
  76.     char digits[10];
  77.     ascii_t *result, *left, *right;
  78.     unsigned int i, j, lh, rh, lw, rw, h, w, id, count;
  79.     if ( t == 0 ) {
  80.         result= (ascii_t *) malloc( sizeof( ascii_t ) );
  81.         result->height= result->width= 1;
  82.         result->pos= 0;
  83.         result->grid[0]= '*';
  84.         return result;
  85.     }
  86.     id= t->id;
  87.     count= 0;
  88.     do {
  89.         digits[count++]= '0' + (id % 10);
  90.         id /= 10;
  91.     } while ( id > 0 );
  92.     left= ascii( t->left );
  93.     right= ascii( t->right );
  94.     if ( left->width < 2 )
  95.         lh= lw= 2;
  96.     else {
  97.         lh= (left->width + 1) >> 1;
  98.         lh= left->width - left->pos;
  99.         lw= left->width;
  100.     }
  101.     if ( right->width < 2 )
  102.         rh= rw= 2;
  103.     else {
  104.         rh= (right->width + 1) >> 1;
  105.         rh= right->pos + 1;
  106.         rw= right->width;
  107.     }
  108.     w= 1 + lw + rw;
  109.     h= lh + left->height >= rh + right->height? lh + left->height : rh + right->height;
  110.     if ( count > h ) h= count;
  111.     result= (ascii_t *) malloc( sizeof( ascii_t ) + w*h - 1 );
  112.     result->height= h;
  113.     result->width= w;
  114.     result->pos= lw;
  115.     for ( i= 0; i < w*h; ++i )
  116.         result->grid[i]= ' ';
  117.     for ( i= 0; i < count; ++i )
  118.         result->grid[ i*w + lw ]= digits[count-i-1];
  119.     for ( i= 0; i < left->height; ++i )
  120.         for ( j= 0; j < left->width; ++j )
  121.             result->grid[ (lh+i)*w+j ]= left->grid[ i*left->width+j ];
  122.     for ( i= 0; i < right->height; ++i )
  123.         for ( j= 0; j < right->width; ++j )
  124.             result->grid[ (rh+i)*w+lw+1+j+(right->width < 2) ]= right->grid[ i*right->width+j ];
  125.     for ( i= 1; i < lh; ++i )
  126.         result->grid[ i*w+lw-i ]= '/';
  127.     for ( i= 1; i < rh; ++i )
  128.         result->grid[ i*w+lw+i ]= '\\';
  129.     free( left );
  130.     free( right );
  131.     return result;
  132. }
  133. void print( tree * t, int tab ) {
  134.     if ( t == 0 ) { printf( "%*s(%c)\n", tab, "", '*' ); return; }
  135.     printf( "%*s%d\n", tab, "", t->id );
  136.     print( t->left, tab+4 );
  137.     print( t->right, tab+4 );
  138.     return;
  139. }
  140. int main( int argc, char *argv[] ) {
  141.     tree *mytree;
  142.     char b[200], *p;
  143.     p= fgets( b, sizeof(b), stdin );
  144.     if ( p == 0 ) return 0;
  145.     mytree= create( &p );
  146.     if ( *p == '\0' || *p == '\n' ) {
  147.         ascii_t *result= ascii( mytree );
  148.         printf( "Downward tree form:\n" );
  149.         display( result );
  150.         printf( "\nSideways tree form:\n" );
  151.         sidedisplay( result );
  152.         printf( "\nTabbed tree form:\n" );
  153.         print( mytree, 0 );
  154.         free( result );
  155.     } else
  156.         printf( "Failed to parse correctly.\n" );
  157.     destroy( mytree );
  158.     return 0;
  159. }
Success #stdin #stdout 0s 2388KB
comments (?)
stdin
copy 
20(10(5()())(17()()))(30(21()())(*))
stdout
copy 
Downward tree form:
           2        
          /0\       
         /   \      
        /     \     
       /       \    
      /         \   
     1           3  
    /0\         /0\ 
   /   \       /   *
  5     1     2     
 / \   /7\   /1\    
*   * *   * *   *   

Sideways tree form:
           *
          / 
         5  
        / \ 
       /   *
      10    
     / \   *
    /   \ / 
   /     17 
  /       \ 
 /         *
20          
 \         *
  \       / 
   \     21 
    \   / \ 
     \ /   *
      30    
       \    
        *   

Tabbed tree form:
20
    10
        5
            (*)
            (*)
        17
            (*)
            (*)
    30
        21
            (*)
            (*)
        (*)
https://ideone.com/eB4ken
Sample tree parser and tree printing code
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!