Pagini recente » Istoria paginii runda/concurs_luigi | Istoria paginii runda/253913/clasament | Istoria paginii runda/tt1/clasament | Cod sursa (job #2012106) | Cod sursa (job #2016703)
#include <cstdio>
using namespace std;
FILE *in,*out;
const int nmax = 100000;
char c[nmax+3];
struct Symbol
{
int tip;
char semn;
int val;
int prior;
} v[1+nmax];
int n;
int jump[1+nmax][3];
int last[1+nmax][3];
int prioritate(char x)
{
if(x == '-' || x == '+')
return 1;
return 2;
}
void parsare()
{
int i = 0, nr = 0, flag = 0;
while(c[i] != '\0')
{
if(c[i] >= '0' && c[i] <= '9') {
if(flag == 0) {
flag = 1;
nr = c[i] - '0';
} else {
nr *= 10;
nr += (c[i] - '0');
}
} else {
if(flag == 1) {
flag = 0;
v[++n].tip = 4;
v[n].val = nr;
}
if(c[i] == '-' || c[i] == '+' || c[i] == '*' || c[i] == '/')
{
v[++n].tip = 3;
v[n].semn = c[i];
v[n].prior = prioritate(c[i]);
}
else if(c[i] == '(')
v[++n].tip = 1;
else if(c[i] == ')')
v[++n].tip = 2;
}
i ++;
}
if(flag == 1) {
v[++n].tip = 4;
v[n].val = nr;
}
}
void precalculare()
{
int level = 0;
jump[1][2] = 0;
jump[1][1] = 0;
for(int j = 1; j <= 2; j ++)
{
for(int i = 2; i <= n; i ++)
{
if(v[i-1].tip == 1)
level ++;
if(v[i].tip == 2)
{
level --;
jump[i][j] = last[level][j];
}
if(v[i].tip == 3)
{
jump[i][j] = last[level][j];
if(v[i].prior == j)
last[level][j] = i;
}
if(v[i].tip == 4)
jump[i][j] = last[level][j];
}
}
}
int root;
int left[1+nmax],right[1+nmax];
int buildtree(int from,int to)
{
if(from == to)
{
return to;
}
else
{
int node = jump[to][1];
if(node == 0 || node < from)
node = jump[to][2];
if(node == 0 || node < from)
return buildtree(from+1,to-1);
else
{
left[node] = buildtree(from,node-1);
right[node] = buildtree(node+1,to);
return node;
}
}
}
int calculare(int node)
{
if(v[node].tip == 3)
{
if(v[node].semn == '+')
return calculare(left[node]) + calculare(right[node]);
if(v[node].semn == '-')
return calculare(left[node]) - calculare(right[node]);
if(v[node].semn == '*')
return calculare(left[node]) * calculare(right[node]);
if(v[node].semn == '/')
return calculare(left[node]) / calculare(right[node]);
}
if(v[node].tip == 4)
{
return v[node].val;
}
}
int main()
{
in = fopen("evaluare.in","r");
out = fopen("evaluare.out","w");
fgets(c,nmax+3,in);
parsare();
precalculare();
root = buildtree(1,n);
fprintf(out,"%d",calculare(root));
return 0;
}