Cod sursa(job #1163358)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 1 aprilie 2014 12:24:17
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 3.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <cassert>

#define fiu1 (nod << 1)
#define fiu2 (fiu1 + 1)
#define mid ((st + dr) >> 1)

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

const int NMAX = 1e5 + 100;
const int oo = 0x3f3f3f3f;

int n, nr, prior[NMAX], ARB[NMAX * 3 + 100], POZ[NMAX * 3+ 100];
char s[NMAX];
int rez;

struct NOD{
    NOD *st, *dr;
    int val;
    NOD(){st = dr = 0; val = 0;}
}* T;

struct element{
    int type, val;
    char c;
}el[NMAX];

void Citire()
{
    int priority = 0;
    fin.getline(s, NMAX);
    for(int i = 0; s[i]; i++)
       if(s[i] == '(') priority += 10;
       else if(s[i] == ')') priority -= 10;
       else if(s[i] == '+' || s[i] == '-')
       {
            ++n;
            el[n].type = 2; // 2 inseamna operatie
            el[n].c = s[i];
            prior[n] = priority + 1;
       }
       else if(s[i] == '*' || s[i] == '/')
       {
            ++n;
            el[n].type = 2; // 2 inseamna operatie
            el[n].c = s[i];
            prior[n] = priority + 10;
       }
       else
       {
           nr = 0; ++n;
           while(s[i] && s[i] >= '0' && s[i] <= '9')
                nr = nr * 10 + s[i] - '0', i++;
           el[n].type = 1; // 1 inseamna un numar
           el[n].val = nr;
           prior[n] = oo;
           i--;
       }
    //for(int i = 1; i <= n; i++)
        //cout << prior[i] << endl;
}

void BuildAI(int nod, int st, int dr)
{
    if(st == dr)
    {
        ARB[nod] = prior[st];
        POZ[nod] = st;
        return;
    }

    BuildAI(fiu1, st, mid);
    BuildAI(fiu2, mid + 1, dr);

    if(ARB[fiu1] > ARB[fiu2])
    {
        ARB[nod] = ARB[fiu2];
        POZ[nod] = POZ[fiu2];
    }
    else
    {
        ARB[nod] = ARB[fiu1];
        POZ[nod] = POZ[fiu1];
    }
}

int Query(int nod, int st, int dr, int left, int right)
{
    if(left > dr || right < st) return 0;
    if(left <= st && dr <= right)
        return POZ[nod];

    int a, b;
    a = Query(fiu1, st, mid, left, right);
    b = Query(fiu2, mid + 1, dr, left, right);
    if(prior[a] < prior[b])
        return a;
    else
        return b;
}

void BuildARB(NOD *&nod, int st, int dr)
{
    if(st > dr) return;
    if(st == dr)
    {
        nod = new NOD;
        nod->val = st;
        return ;
    }

    nod = new NOD;
    int poz = Query(1, 1, n, st, dr);
    nod->val = poz;

    BuildARB(nod->st, st, poz - 1);
    BuildARB(nod->dr, poz + 1, dr);
}

int Eval(NOD *nod)
{
    if(!nod->st && !nod->dr)
        return el[nod->val].val;
    int a = Eval(nod->st), b = Eval(nod->dr);
    assert(b);
    switch(el[nod->val].c)
    {
        case '+' : return a + b; break;
        case '-' : return a - b; break;
        case '*' : return a * b; break;
        case '/' : return a / b; break;
    }
}

int main()
{
    Citire();
    BuildAI(1, 1, n);
    prior[0] = oo + oo;
    BuildARB(T, 1, n);
    fout << Eval(T);
    return 0;
}