Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.0 kB
0
Indexable
Never
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

int ans;

typedef struct Node_{
    struct Node_* left,*right;
    char data;
    int id;
}Node;

void buildTree(Node* root){
    char c;
    root->left=(Node*)malloc(sizeof(Node));
    root->left->left=root->left->right=NULL;
    root->right=(Node*)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->id=c-'0';
    }
    scanf(" %c",&c);
    root->right->data=c;
    if(c=='+' || c=='-' || c=='*'){
        buildTree(root->right);
    }
    else{
        root->right->id=c-'0';
    }

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

void freeTree(Node* root){
    if(root!=NULL){
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

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

    if(root->data=='+') root->id=root->left->id + node->left->id;
    else if(root->data=='-') root->id=root->left->id - node->left->id;
    else if(root->data=='*') root->id=root->left->id * node->left->id;
    
    if(node->data=='+') node->id=root->id + node->right->id;
    else if(node->data=='-') node->id=root->id - node->right->id;
    else if(node->data=='*') node->id=root->id * node->right->id;

    root->right=node->left;
    node->left=root;

    if(node->id < ans) ans=node->id;
}

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

    if(root->data=='+') root->id=node->right->id + root->right->id;
    else if(root->data=='-') root->id=node->right->id - root->right->id;
    else if(root->data=='*') root->id=node->right->id * root->right->id;
    
    if(node->data=='+') node->id=node->left->id + root->id;
    else if(node->data=='-') node->id=node->left->id - root->id;
    else if(node->data=='*') node->id=node->left->id * root->id;

    root->left=node->right;
    node->right=root;

    if(node->id < ans) ans=node->id;
}

Node* Spin(Node* root){
    Node* next;

    while(root->right->data=='+' || root->right->data=='-' || root->right->data=='*'){
        next=root->right;
        leftSpin(root);
        root=next;
    }
    while(root->left->data=='+' || root->left->data=='-' || root->left->data=='*'){
        next=root->left;
        rightSpin(root);
        root=next;
    }
    return root;
}

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

    scanf(" %c",&c);
    root->data=c;
    buildTree(root);
    ans=root->id;

    root=Spin(root);
    printf("%d\n",ans);

    freeTree(root);

    return 0;
}