Cod sursa(job #1319155)

Utilizator retrogradLucian Bicsi retrograd Data 16 ianuarie 2015 18:32:46
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include<fstream>
#include<vector>
#include<utility>
#include<algorithm>

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

struct Oper {
    char op;
    int n, p;
    Oper(char c, int a, int b) {op = c; n = a; p = b;}
    Oper() {}
};


vector<int> NUM;
vector<Oper> OP;
int nrop;

char c[MAXN];



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;
    }
}

bool cmp(const Oper &a, const Oper &b) {
    if(a.p > b.p) return 1;
    if(a.p == b.p && a.n < b.n) return 1;
    return 0;
}

int PARENT[MAXN], RANK[MAXN];
int Find(int i) {
    while(PARENT[i]) i = PARENT[i];
    return i;
}
void Union(int i, int j, int val) {
    i = Find(i);
    j = Find(j);
    if(RANK[i] < RANK[j]) {
        PARENT[i] = j;
        NUM[j] = val;
    } else {
        PARENT[j] = i;
        NUM[i] = val;
        if(RANK[i] == RANK[j])
            RANK[i]++;
    }
}

int main() {
    fin.getline(c, MAXN);
    int priority = 0, i;
    OP.push_back(Oper());
    NUM.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(Oper('*', NUM.size() - 1, 2 + priority)); break;
                case '+': OP.push_back(Oper('+', NUM.size() - 1, 1 + priority)); break;
                case '/': OP.push_back(Oper('/', NUM.size() - 1, 2 + priority)); break;
                case '-': OP.push_back(Oper('-', NUM.size() - 1, 1 + priority)); break;
                case '(': priority += 10; break;
                case ')': priority -= 10; break;
            }

        }
    }
    nrop = OP.size() - 1;
    sort(OP.begin() + 1, OP.end(), cmp);
    int val = 0;
    int res;
    for(int i=1; i<=nrop; i++) {
        int p1 = OP[i].n;
        int p2 = OP[i].n+1;
        p1 = Find(p1);
        p2 = Find(p2);
        Union(p1, p2, calc(NUM[p1], NUM[p2], OP[i].op));
    }
    fout<<NUM[Find(1)];

    return 0;
}