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

struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct ListNode {
    struct TreeNode *node;
    struct ListNode *next;
};

void padding ( char ch, int n )
{
  int i;
  for ( i = 0; i < n; i++ )
    putchar ( ch );
}
void structure ( struct TreeNode *root, int level )
{
  int i;
  if ( root == NULL ) {
    padding ( '\t', level );
    puts ( "~" );
  }
  else {
    structure ( root->right, level + 1 );
    padding ( '\t', level );
    printf ( "%c\n", root->data );
    structure ( root->left, level + 1 );
  }
}

struct TreeNode *createTreeNode(char c) {
    struct TreeNode *newNode = (struct TreeNode*) malloc(sizeof(struct TreeNode));

    if(!newNode) { // newNode != NULL
        printf("Error allocating memory\n");
        exit(1);
    }

    newNode -> data = c;
    newNode -> left = newNode -> right = NULL;

    return newNode;
}

struct ListNode *createListNode(struct TreeNode *data) {
    struct ListNode *newNode = (struct ListNode*) malloc(sizeof(struct ListNode));

    if(!newNode) { // newNode != NULL
        printf("Error allocating memory\n");
        exit(1);
    }

    newNode -> node = data;
    newNode -> next = NULL;

    return newNode;
}

void push(struct ListNode **head, struct TreeNode *data) {
    struct ListNode *newNode = createListNode(data);

    newNode -> next = *head;
    *head = newNode;
}

struct TreeNode *pop(struct ListNode **head) {
    if (*head == NULL) return NULL;

    struct TreeNode *node = (*head) -> node;

    struct ListNode *dummy = *head;
    *head = (*head) -> next;
    free(dummy);

    return node;
}

int isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int isDigit(char c) {
    return c >= '0' && c <= '9';
}

struct TreeNode *createExpressionTrie() {
    struct ListNode *stack = NULL;
    int c;

    while((c = getchar()) != EOF) {
        if (c == '(') continue;

        if (c == ')') {
            struct TreeNode *rightOperand = pop(&stack);
            struct TreeNode *operator = pop(&stack);
            struct TreeNode *leftOperand = pop(&stack);

            operator -> left = leftOperand;
            operator -> right = rightOperand;

            push(&stack, operator);
        }
        else if(isOperator(c) || isDigit(c)) {
            // operator || number
            struct TreeNode *node = createTreeNode(c);
            push(&stack, node);
        }
        else {
            printf("Invalid character [%c]\n", c);
            return NULL;
        }
    }

    return pop(&stack);
}

int calculateExpression(struct TreeNode *root) {
    if (!root) return 0;

    int left = calculateExpression(root->left);
    int right = calculateExpression(root-> right);

    if (isOperator(root->data)) {
        int value;
        
        switch (root->data) {
            case '+':
                value = left + right;
                break;
            case '-':
                value = left - right;
                break;
            case '*':
                value = left * right;
                break;
            case '/':
                value = left / right;
                break;
            default:
                break;
        }
        
        return value;
    }
    
    return root -> data - '0';
}

int main() {

    struct TreeNode *root = createExpressionTrie();

    if(!root) return 1;

    structure(root, 0);
    printf("--------------------------\n");
    printf("Expression result: %d\n", calculateExpression(root));
    

    return 0;
}