Untitled

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

int ans;

typedef struct node {
    struct node* left;
    struct node* right;
    int num;
    char data;
} Node;

void buildTree(Node* root) {
    char c;
    root->left = malloc(sizeof(Node));
    root->left->left = root->left->right = NULL;
    root->right = malloc(sizeof(Node));
    root->right->left = root->right->right = NULL;

    scanf(" %c", &c);
    root->left->data = c;
    if (c == '+' || c == '-' || c == '*') {
        buildTree(root->left);
    }
    else {
        root->left->num = c - '0';
    }

    scanf(" %c", &c);
    root->right->data = c;
    if (c == '+' || c == '-' || c == '*') {
        buildTree(root->right);
    }
    else {
        root->right->num = c - '0';
    }


    if (root->data == '+')      root->num = root->left->num + root->right->num;
    else if (root->data == '-') root->num = root->left->num - root->right->num;
    else if (root->data == '*') root->num = root->left->num * root->right->num;
}

void printTree(Node* root) {
    if (root == NULL) return;
    printf("%c", root->data);
    printTree(root->left);
    printTree(root->right);
}

void freeTree(Node* root) {
    if (root == NULL) return;

    freeTree(root->left);
    freeTree(root->right);
    free(root);
}


void leftSpin(Node* root) {
    Node* newRoot = root->right;

    if (root->data == '+')      root->num = root->left->num + newRoot->left->num;
    else if (root->data == '-') root->num = root->left->num - newRoot->left->num;
    else if (root->data == '*') root->num = root->left->num * newRoot->left->num;

    if (newRoot->data == '+')       newRoot->num = root->num + newRoot->right->num;
    else if (newRoot->data == '-')  newRoot->num = root->num - newRoot->right->num;
    else if (newRoot->data == '*')  newRoot->num = root->num * newRoot->right->num;

    root->right = newRoot->left;
    newRoot->left = root;

    if (newRoot->num < ans) ans = newRoot->num;
}

void rightSpin(Node* root) {
    Node* newRoot = root->left;

    if (root->data == '+')      root->num = newRoot->right->num + root->right->num;
    else if (root->data == '-') root->num = newRoot->right->num - root->right->num;
    else if (root->data == '*') root->num = newRoot->right->num * root->right->num;

    if (newRoot->data == '+')        newRoot->num = newRoot->left->num + root->num;
    else if (newRoot->data == '-')   newRoot->num = newRoot->left->num - root->num;
    else if (newRoot->data == '*')   newRoot->num = newRoot->left->num * root->num;

    root->left = newRoot->right;
    newRoot->right = root;

    if (newRoot->num < ans) ans = newRoot->num;
}


Node* Spin(Node* root) {
    Node* nxt;
    // if we can continue leftSpin
    while (root->right->data == '+' || root->right->data == '-' || root->right->data == '*') {
        nxt = root->right;
        leftSpin(root);
        root = nxt;
    }

    // if we can continue rightSpin
    while (root->left->data == '+' || root->left->data == '-' || root->left->data == '*') {
        nxt = root->left;
        rightSpin(root);
        root = nxt;
    }

    return root;
}

int main() {
    int n;
    char c;
    scanf("%d", &n);
    Node* root = malloc(sizeof(Node));

    // scan root
    scanf(" %c", &c);
    root->data = c;

    // build tree and initialize ans
    buildTree(root);
    ans = root->num;

    // spin tree and output ans
    root = Spin(root);
    printf("%d\n", ans);

    // check whether we build tree correctly
    // printTree(root);
    // printf("\n");

    // free space
    freeTree(root);

    return 0;
}