Cod sursa(job #1318979)

Utilizator retrogradLucian Bicsi retrograd Data 16 ianuarie 2015 15:43:06
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.67 kb
#include<fstream>

#define MAXN 100001
#define INF 100000000

using namespace std;


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

struct Node {
    int min, pos;
    Node(int a, int b) {min = a; pos = b;}
    Node() {}
};

int NUM[MAXN];
char OP[MAXN];
int PRI[MAXN];
Node TREE[MAXN*17];
char c[MAXN];
int nrnum = 0, nrop = 0;

int m;
void buildtree(int node, int b, int e) {
    if(b == e) {TREE[node] = Node(PRI[b], b); return;}

    m = (b+e)/2;
    buildtree(node*2, b, m);
    buildtree(node*2+1, m+1, e);
    if(TREE[node*2].min <= TREE[node*2+1].min) {
        TREE[node] = TREE[node*2];
    } else {
        TREE[node] = TREE[node*2+1];
    }
}

Node min1, min2;
Node rmq(int node, int b, int e, int l, int r) {
    if(r<b || l>e) return Node(INF, -1);
    if(e<=r && b>=l) return TREE[node];
    m = (b+e)/2;

    min1 = rmq(node*2, b, m, l, r);
    min2 = rmq(node*2+1, m+1, e, l, r);

    if(min1.min <= min2.min) {
        return min1;
    } else {
        return min2;
    }
}

int calc(int a, int b, char op) {
    switch(op) {
        case '+': return a+b;
        case '-': return a-b;
        case '*': return a*b;
        case '/': return a/b;
    }
}


int solve(int b, int e) {
    if(b == e) return calc(NUM[b], NUM[b+1], OP[b]);
    else {
        Node nod = rmq(1, 1, nrop, b, e);
        int S1, S2;
        if(b<nod.pos)
            S1 = solve(b, nod.pos - 1);
        else S1 = NUM[b];
        if(nod.pos<e)
            S2 = solve(nod.pos + 1, e);
        else S2 = NUM[e+1];

        return calc(S1, S2, OP[nod.pos]);
    }
}

int main() {
    fin.getline(c, MAXN);
    int priority = 0, i;
    for(int i=0; c[i]; i++) {
        if(isdigit(c[i])) {
            nrnum++;
            while(isdigit(c[i])) {
                NUM[nrnum] = NUM[nrnum]*10+c[i] - '0';
                i++;
            }
            i--;
        } else {
            switch(c[i]) {
                case '*': OP[++nrop] = '*'; PRI[nrop] = 2 + priority; break;
                case '+': OP[++nrop] = '+'; PRI[nrop] = 1 + priority; break;
                case '/': OP[++nrop] = '/'; PRI[nrop] = 2 + priority; break;
                case '-': OP[++nrop] = '-'; PRI[nrop] = 1 + priority; break;
                case '(': priority += 10; break;
                case ')': priority -= 10; break;
            }

        }
    }
    /*
    for(int i=1; i<=nrnum; i++) fout<<NUM[i]<<" ";
    fout<<endl;
    for(int i=1; i<=nrop; i++) fout<<OP[i]<<" ";
    fout<<endl;
    for(int i=1; i<=nrop; i++) fout<<PRI[i]<<" ";
    fout<<endl;
    */

    buildtree(1, 1, nrop);
    fout<<solve(1, nrop);

    return 0;
}