Cod sursa(job #2896924)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 1 mai 2022 15:30:19
Problema Evaluarea unei expresii Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
//Ilie Dumitru
#include<cstdio>
#include<cstring>
typedef long long int ll;
const int NMAX=100005;
const ll MOD=1000000007;

FILE* f=fopen("evaluare.in", "r"), *g=fopen("evaluare.out", "w");

struct node
{
    int val;
    char op;
    node* l, *r;
};

int eval(node* n)
{
    if(!n)
        return 0;
    switch(n->op)
    {
        case '+':
            return eval(n->l)+eval(n->r);
        case '-':
            return eval(n->l)-eval(n->r);
        case '*':
            return eval(n->l)*eval(n->r);
        case '/':
            return eval(n->l)/eval(n->r);
        default:
            return n->val;
    }
}

void print(node* n)
{
    if(n->op)
    {
        if((n->l->op=='+' || n->l->op=='-') && (n->op=='*' || n->op=='/'))
        {
            printf("(");
            print(n->l);
            printf(")");
        }
        else
            print(n->l);
        printf("%c", n->op);
        if(((n->r->op=='+' || n->r->op=='-') && (n->op=='*' || n->op=='/')) || ((n->op=='-' || n->op=='/') && n->r->op))
        {
            printf("(");
            print(n->r);
            printf(")");
        }
        else
            print(n->r);
    }
    else
        printf("%d", n->val);
}

char expr[NMAX];
int priorities[NMAX];

void computePriorities()
{
    int i, prnt=0, prioritPerParant=2;
    for(i=0;expr[i];++i)
    {
        if(expr[i]=='(')
            prnt+=prioritPerParant;
        else if(expr[i]==')')
            prnt-=prioritPerParant;
        else if(expr[i]=='+' || expr[i]=='-')
            priorities[i]=prnt+1;
        else if(expr[i]=='*' || expr[i]=='/')
            priorities[i]=prnt+2;
    }
}

node* computeTree(int start, int end) // [start, end]
{
    int i, minPr=(-1)^(1<<31), posMinPr=start-1;
    for(i=end;i>=start;--i)
        if(priorities[i] && priorities[i]<minPr)
            posMinPr=i, minPr=priorities[i];
    node* n=new node;
    n->val=0;
    n->op=0;
    n->l=0;
    n->r=0;
    if(posMinPr==start-1)
    {
        //val
        for(i=start;i<=end;++i)
            if(expr[i]>='0' && expr[i]<='9')
                n->val=n->val*10+expr[i]-'0';
    }
    else
    {
        //op
        n->op=expr[posMinPr];
        n->l=computeTree(start, posMinPr-1);
        n->r=computeTree(posMinPr+1, end);
    }
    return n;
}

void clearMem(node*& n)
{
    if(n->op)
    {
        clearMem(n->l);
        clearMem(n->r);
    }
    delete n;
}

int main()
{
    fgets(expr, NMAX, f);
    int l=strlen(expr);
    if(expr[l-1]=='\n')
        expr[--l]=0;
    computePriorities();
    node* tree=computeTree(0, l-1);
    //print(tree);
    fprintf(g, "%d", eval(tree));
    clearMem(tree);
    fclose(f);
    fclose(g);
    return 0;
}