Pagini recente » Cod sursa (job #2964674) | Cod sursa (job #941322) | Cod sursa (job #2741727) | Cod sursa (job #1035677) | Cod sursa (job #1319155)
#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;
}