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

typedef struct cvor
{
    union sadrzaj
    {
        int broj;
        char znak;
    } sadrzaj;
    
    struct cvor *l, *d;
} cvor;

typedef struct element
{
    cvor *izraz;
    struct element *s;

} element;

void push( element **stek, cvor *novi )
{
    element *pom = ( element * ) malloc( sizeof( element ) );
    pom -> izraz = novi;
    pom -> s = *stek;
    *stek = pom;
}

void pop( element **stek, cvor **izraz )
{
    element *pom = *stek;
    *izraz = ( *stek ) -> izraz;
    *stek = ( *stek ) -> s;
    free( pom );
}

void ulaz( cvor **koren )
{
    char c;
    element *stek = NULL;
    int broj = 0;
    while( ( c = getchar() ) != EOF )
    {
        if( c <= '9' && c >= '0' ) broj = broj * 10 + c - '0';
        else if( c == '+' || c == '-' || c == '*' || c == '/' )
        {
            if( broj )
            {
                cvor *novi = ( cvor * )malloc( sizeof( cvor ) );
                novi -> sadrzaj.broj = broj;
                novi -> l = novi -> d = NULL;
                push( &stek, novi );
                broj = 0;         
            }

            cvor *novi = ( cvor * )malloc( sizeof(cvor) );
            novi -> sadrzaj.znak = c;
            novi -> l = novi -> d = NULL;
            push( &stek, novi );
        }
        else if( c == ')' )
        {
            if( broj )
            {
                cvor *novi = ( cvor * )malloc( sizeof( cvor ) );
                novi -> sadrzaj.broj = broj;
                novi -> l = novi -> d = NULL;
                push( &stek, novi );
                broj = 0;         
            }

            cvor *izraz1;
            pop( &stek, &izraz1 );
            cvor *operacija;
            pop( &stek, &operacija );
            cvor *izraz2;
            pop( &stek, &izraz2 );

            operacija -> l = izraz2;
            operacija -> d = izraz1;
            push( &stek, operacija );
        }
    }

    *koren = stek -> izraz;
}

void ispis( cvor *koren ){
    if( koren -> l && koren -> d )
    {
        putchar( '(' );
        ispis( koren -> l );
        putchar( koren -> sadrzaj.znak );
        ispis( koren->d );
        putchar( ')' );
    }
    else printf("%d", koren -> sadrzaj.broj );
}

int izracunaj( cvor *koren )
{
    if( koren -> l )
    {
        int l = izracunaj( koren -> l );
        int d = izracunaj( koren -> d );
        if( koren -> sadrzaj.znak == '+' ) return l + d;
        else if( koren -> sadrzaj.znak == '*' ) return l * d;
        else if( koren -> sadrzaj.znak == '-' ) return l - d;
        else return l / d;
    }
    
    return koren -> sadrzaj.broj;
}

void razmak( char c, int n )
{
    for( int i = 0; i < n; i ++ ) putchar( c );
}

void vizuelniPrikaz( cvor *koren, int nivo )
{
    if( !koren )
    {
        razmak('\t', nivo );
        puts("~");
    }
    else
    {
        vizuelniPrikaz( koren -> d, nivo + 1 );
        razmak('\t', nivo );
        if( koren -> l ) printf("%c\n", koren -> sadrzaj.znak );
        else printf("%d\n", koren -> sadrzaj.broj ); 
        vizuelniPrikaz( koren -> l, nivo + 1 );
    }
}

int main(){
    cvor *koren = NULL;
    ulaz( &koren );

    vizuelniPrikaz( koren, 0 );

    printf("%d\n", izracunaj( koren ) ); 
    ispis( koren );

    return 0;
}