Pagini recente » Autentificare | Cod sursa (job #424540) | Cod sursa (job #389623) | Istoria paginii runda/cerculetz_02/clasament | Cod sursa (job #867514)
Cod sursa(job #867514)
// Include
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
// Definitii
#define leftSon (node<<1)
#define rightSon (node<<1)+1
// Constante
const int sz = (int)1e5+1;
const int treesz = sz<<2;
const int oo = (1<<30)-1;
// Functii
int RSD(int left, int right);
void update(int node, int left, int right);
void query(int node, int left, int right);
// Variabile
ifstream in("evaluare.in");
ofstream out("evaluare.out");
char expresion[sz];
int operatorsNum;
int operatorsID[sz];
int leftRange, rightRange;
int pos;
struct opr
{
int grade;
int id;
bool operator< (opr a)
{
if(grade == a.grade)
return id > a.id;
return grade < a.grade;
}
} tree[treesz], val;
// Main
int main()
{
in >> expresion;
for(int i=1 ; i<=treesz ; ++i)
tree[i].grade = oo;
int expLen = strlen(expresion);
int bracketsLevel = 0;
for(int i=0 ; i<expLen ; ++i)
if(expresion[i] == '+' || expresion[i] == '-' || expresion[i] == '*' || expresion[i] == '/')
++operatorsNum;
int currentOPs = 0;
for(int i=0 ; i<expLen ; ++i)
{
switch(expresion[i])
{
case '(':
{
++bracketsLevel;
break;
}
case ')':
{
--bracketsLevel;
break;
}
case '+':
case '-':
{
int currentGrade = bracketsLevel*2;
operatorsID[++currentOPs] = i;
pos = currentOPs;
val.grade = currentGrade;
val.id = pos;
update(1, 1, operatorsNum);
break;
}
case '*':
case '/':
{
int currentGrade = bracketsLevel*2 + 1;
operatorsID[++currentOPs] = i;
pos = currentOPs;
val.grade = currentGrade;
val.id = pos;
update(1, 1, operatorsNum);
break;
}
}
}
operatorsID[operatorsNum+1] = oo;
out << RSD(0, expLen-1);
in.close();
out.close();
return 0;
}
int RSD(int left, int right)
{
int operatorGrade=oo, operatorPos;
leftRange = lower_bound(operatorsID+1, operatorsID+operatorsNum+1, left) - operatorsID;
rightRange = upper_bound(operatorsID+1, operatorsID+operatorsNum+1, right) - operatorsID - 1;
if(leftRange <= rightRange)
{
val.grade = oo;
val.id = 0;
query(1, 1, operatorsNum);
operatorGrade = val.grade;
operatorPos = operatorsID[val.id];
left = RSD(left, operatorPos-1);
right = RSD(operatorPos+1, right);
switch(expresion[operatorPos])
{
case '+': return left+right;
case '-': return left-right;
case '*': return left*right;
case '/': return left/right;
}
}
int num = 0;
for(int i=left ; i<=right ; ++i)
if(expresion[i] != '(' && expresion[i] !=')')
num = num*10 + (expresion[i]-48);
return num;
}
void update(int node, int left, int right)
{
if(left == right)
{
tree[node] = val;
return;
}
int mid = (left + right) >> 1;
if(pos <= mid)
update(leftSon, left, mid);
else
update(rightSon, mid+1, right);
tree[node] = (tree[leftSon] < tree[rightSon])? tree[leftSon] : tree[rightSon];
}
void query(int node, int left, int right)
{
if(leftRange <= left && right <= rightRange)
{
if(tree[node] < val)
val = tree[node];
return;
}
int mid = (left + right) >> 1;
if(leftRange <= mid)
query(leftSon, left, mid);
if(mid < rightRange)
query(rightSon, mid+1, right);
}