Cod sursa(job #1319028)

Utilizator retrogradLucian Bicsi retrograd Data 16 ianuarie 2015 16:50:58
Problema Evaluarea unei expresii Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.15 kb
#include<fstream>
#include<vector>

#define MAXN 100001
#define INF 1000000000

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() {}
};

vector<int> NUM;
vector<char> OP;
vector<int> PRI;
vector<Node> TREE;
int nrop;

char c[MAXN];


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

    int 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];
    int m = (b+e)/2;

    Node min1 = rmq(node*2, b, m, l, r);
    Node 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]);
    }
}

void afis(int node, int b, int e) {
    fout<<"["<<b<<", "<<e<<"] -> "<<TREE[node].min<<", "<<TREE[node].pos<<endl;
    if(b == e) return;
    afis(node*2, b, (b+e)/2);
    afis(node*2+1, (b+e)/2+1, e);
}

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

        }
        priority --;
    }
    nrop = OP.size()-1;
    if(nrop == 0) {
        fout<<NUM[1];
    }
    TREE.resize(nrop*2);
/*
    for(int i=1; i<=nrop+1; 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);

    //afis(1, 1, nrop);

    fout<<solve(1, nrop);

    return 0;
}