Pagini recente » Cod sursa (job #2243941) | Cod sursa (job #330810) | Cod sursa (job #738767) | Cod sursa (job #2423734) | Cod sursa (job #2896924)
//Ilie Dumitru
#include<cstdio>
#include<cstring>
typedef long long int ll;
const int NMAX=100005;
const ll MOD=1000000007;
FILE* f=fopen("evaluare.in", "r"), *g=fopen("evaluare.out", "w");
struct node
{
int val;
char op;
node* l, *r;
};
int eval(node* n)
{
if(!n)
return 0;
switch(n->op)
{
case '+':
return eval(n->l)+eval(n->r);
case '-':
return eval(n->l)-eval(n->r);
case '*':
return eval(n->l)*eval(n->r);
case '/':
return eval(n->l)/eval(n->r);
default:
return n->val;
}
}
void print(node* n)
{
if(n->op)
{
if((n->l->op=='+' || n->l->op=='-') && (n->op=='*' || n->op=='/'))
{
printf("(");
print(n->l);
printf(")");
}
else
print(n->l);
printf("%c", n->op);
if(((n->r->op=='+' || n->r->op=='-') && (n->op=='*' || n->op=='/')) || ((n->op=='-' || n->op=='/') && n->r->op))
{
printf("(");
print(n->r);
printf(")");
}
else
print(n->r);
}
else
printf("%d", n->val);
}
char expr[NMAX];
int priorities[NMAX];
void computePriorities()
{
int i, prnt=0, prioritPerParant=2;
for(i=0;expr[i];++i)
{
if(expr[i]=='(')
prnt+=prioritPerParant;
else if(expr[i]==')')
prnt-=prioritPerParant;
else if(expr[i]=='+' || expr[i]=='-')
priorities[i]=prnt+1;
else if(expr[i]=='*' || expr[i]=='/')
priorities[i]=prnt+2;
}
}
node* computeTree(int start, int end) // [start, end]
{
int i, minPr=(-1)^(1<<31), posMinPr=start-1;
for(i=end;i>=start;--i)
if(priorities[i] && priorities[i]<minPr)
posMinPr=i, minPr=priorities[i];
node* n=new node;
n->val=0;
n->op=0;
n->l=0;
n->r=0;
if(posMinPr==start-1)
{
//val
for(i=start;i<=end;++i)
if(expr[i]>='0' && expr[i]<='9')
n->val=n->val*10+expr[i]-'0';
}
else
{
//op
n->op=expr[posMinPr];
n->l=computeTree(start, posMinPr-1);
n->r=computeTree(posMinPr+1, end);
}
return n;
}
void clearMem(node*& n)
{
if(n->op)
{
clearMem(n->l);
clearMem(n->r);
}
delete n;
}
int main()
{
fgets(expr, NMAX, f);
int l=strlen(expr);
if(expr[l-1]=='\n')
expr[--l]=0;
computePriorities();
node* tree=computeTree(0, l-1);
//print(tree);
fprintf(g, "%d", eval(tree));
clearMem(tree);
fclose(f);
fclose(g);
return 0;
}