Pagini recente » Cowfood | Cod sursa (job #3040969) | Cod sursa (job #1179872) | Cod sursa (job #1351838) | Cod sursa (job #1163353)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#define fiu1 (nod << 1)
#define fiu2 (fiu1 + 1)
#define mid ((st + dr) >> 1)
using namespace std;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
const int NMAX = 1e5 + 100;
const int oo = 0x3f3f3f3f;
long long n, nr, prior[NMAX], ARB[NMAX * 3 + 100], POZ[NMAX * 3+ 100];
char s[NMAX];
int rez;
struct NOD{
NOD *st, *dr;
int val;
NOD(){st = dr = 0; val = 0;}
}* T;
struct element{
int type, val;
char c;
}el[NMAX];
void Citire()
{
int priority = 0;
fin.getline(s, NMAX);
for(int i = 0; s[i]; i++)
if(s[i] == '(') priority += 10;
else if(s[i] == ')') priority -= 10;
else if(s[i] == '+' || s[i] == '-')
{
++n;
el[n].type = 2; // 2 inseamna operatie
el[n].c = s[i];
prior[n] = priority + 1;
}
else if(s[i] == '*' || s[i] == '/')
{
++n;
el[n].type = 2; // 2 inseamna operatie
el[n].c = s[i];
prior[n] = priority + 10;
}
else
{
nr = 0; ++n;
while(s[i] && s[i] >= '0' && s[i] <= '9')
nr = nr * 10 + s[i] - '0', i++;
el[n].type = 1; // 1 inseamna un numar
el[n].val = nr;
prior[n] = oo;
i--;
}
//for(int i = 1; i <= n; i++)
//cout << prior[i] << endl;
}
void BuildAI(int nod, int st, int dr)
{
if(st == dr)
{
ARB[nod] = prior[st];
POZ[nod] = st;
return;
}
BuildAI(fiu1, st, mid);
BuildAI(fiu2, mid + 1, dr);
if(ARB[fiu1] > ARB[fiu2])
{
ARB[nod] = ARB[fiu2];
POZ[nod] = POZ[fiu2];
}
else
{
ARB[nod] = ARB[fiu1];
POZ[nod] = POZ[fiu1];
}
}
int Query(int nod, int st, int dr, int left, int right)
{
if(left > dr || right < st) return 0;
if(left <= st && dr <= right)
return POZ[nod];
int a, b;
a = Query(fiu1, st, mid, left, right);
b = Query(fiu2, mid + 1, dr, left, right);
if(prior[a] < prior[b])
return a;
else
return b;
}
void BuildARB(NOD *&nod, int st, int dr)
{
if(st > dr) return;
if(st == dr)
{
nod = new NOD;
nod->val = st;
return ;
}
nod = new NOD;
int poz = Query(1, 1, n, st, dr);
nod->val = poz;
BuildARB(nod->st, st, poz - 1);
BuildARB(nod->dr, poz + 1, dr);
}
int Eval(NOD *nod)
{
if(!nod->st && !nod->dr)
return el[nod->val].val;
int a = Eval(nod->st), b = Eval(nod->dr);
switch(el[nod->val].c)
{
case '+' : return a + b; break;
case '-' : return a - b; break;
case '*' : return a * b; break;
case '/' : return a / b; break;
}
}
int main()
{
Citire();
BuildAI(1, 1, n);
prior[0] = oo + oo;
BuildARB(T, 1, n);
fout << Eval(T);
return 0;
}