Cod sursa(job #1397189)

Utilizator retrogradLucian Bicsi retrograd Data 23 martie 2015 12:31:18
Problema Eval Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.37 kb
#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;
typedef int var;

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

#define MAXN 30

struct Op {
    var type;
    var p;
    var no;
    Op(var a, var b, var c) {
        type = a;
        no = b;
        p = c;
    }
};

char expr[100000];
var NUM[MAXN];
var NO[100000], nrt;
vector<Op> OP;

char TOP[] = " +-*^+-";

void parse() {
    var cur_nr = 0;
    var priority = 0;
    for(var c=0; expr[c]; c++) {
        char i = expr[c];
        if(isalpha(i)) {
            cur_nr++;
            NO[cur_nr] = i - 'a';
        } else if(i == '+' || i == '-') {

            if(strchr("*+-[(", expr[c-1])) {
                    //operator unar
                    if(i == '-')
                        OP.push_back(Op(6, cur_nr + 1, priority + 3));
                    else
                        OP.push_back(Op(5, cur_nr+1, priority+3));
            } else {
                //operator binar
                if(i == '-')
                    OP.push_back(Op(2, cur_nr, priority));
                else
                    OP.push_back(Op(1, cur_nr, priority));
            }
        } else if(i == '*') {
            OP.push_back(Op(3, cur_nr, priority+1));
        } else if(i == '[') {
            priority += 10;
        } else if(i == ']') {
            priority -= 10;
            OP.push_back(Op(4, cur_nr, priority+2));
        } else if(i == '(') {
            priority += 10;
        } else {
            priority -= 10;
        }
    }
    nrt = cur_nr;
}

var Parent[100000], Rank[100000], Rez[100000];

var Find(var n) {
    if(!Parent[n]) return n;
    Parent[n] = Find(Parent[n]);
    return Parent[n];
}

void Union(var r1, var r2, var under) {
    r1 = Find(r1);
    r2 = Find(r2);

    if(Rank[r1] < Rank[r2]) {
        Parent[r1] = r2;
        Rez[r2] = under;
        Rez[r1] = 0;
    } else {
        Parent[r2] = r1;
        Rez[r1] = under;
        Rez[r2] = 0;
        Rank[r1] += (Rank[r1] == Rank[r2]);
    }
}


void solve(Op op) {

    var a, b;

    switch(op.type) {
    case 1 : // "+"
        a = Find(op.no);
        b = Find(op.no + 1);
        Union(a, b, Rez[a] + Rez[b]);
        break;
    case 2 : // "-"
        a = Find(op.no);
        b = Find(op.no + 1);
        Union(a, b, Rez[a] - Rez[b]);
        break;
    case 3 : // "*"
        a = Find(op.no);
        b = Find(op.no + 1);
        Union(a, b, Rez[a] * Rez[b]);
        break;
    case 4 : // "^"
        a = Find(op.no);
        Rez[a] = Rez[a] * Rez[a];
    case 5 : // "unar+"
        break;
    case 6 : // "unar-"
        a = Find(op.no);
        Rez[a] = -Rez[a];
        break;
    }

}

int main() {

    var n;

    fin>>n;
    for(var i=0; i<n; i++) {
        fin>>NUM[i];
    }

    var cur_nr = 0;
    fin>>expr;

    parse();
/*
    for(var i=1; i<=nrt; i++) {
        fout<<NO[i]<<" ";
    }

    for(auto op : OP) {
        if(op.type > 4) fout<<"unar";

        fout<<TOP[op.type]<<" "<<op.no<<" "<<op.p<<'\n';
    }
*/
    sort(OP.begin(), OP.end(), [](Op a, Op b) {
            return a.p > b.p;
         });

    for(var i=1; i<=nrt; i++) {
        Rez[i] = NUM[NO[i]];
    }

    for(auto op : OP) {
        solve(op);
    }

    fout<<Rez[Find(1)];

    return 0;
}