Pagini recente » Cod sursa (job #2156688) | Cod sursa (job #1093643)
#include <fstream>
#include <cstring>
#include <stack>
#define NMAX 100005
using namespace std;
//expresion trees
FILE* f=freopen("evaluare.in","r",stdin);
FILE* o=freopen("evaluare.out","w",stdout);
struct Tree {
char type;
char op;
int number;
Tree *left,*right;
Tree(char a=0, char b=0, int c=0, Tree *d=0, Tree *e=0) :
type(a),op(b),number(c),left(d),right(e) {}
} *A;
typedef Tree * TREE;
char exp[NMAX];
int l;
stack<TREE> stk;
stack<char> op;
char sign[]="+-*/",prsign[]="*/";
void ToTree()
{
int i;
for(i=0;i<l;++i)
{
char c=exp[i];
switch(c)
{
case '+':case '-':
while(!op.empty()&&strchr(sign,op.top()))
{
Tree *r=stk.top(); stk.pop();
Tree *l=stk.top(); stk.pop();
Tree *x=new Tree('o',op.top(),0,l,r);
op.pop();
stk.push(x);
}
op.push(c);
break;
case '*':case '/':
if(!op.empty()&&strchr(prsign,op.top()))
{
Tree *r=stk.top(); stk.pop();
Tree *l=stk.top(); stk.pop();
Tree *x=new Tree('o',op.top(),0,l,r);
op.pop();
stk.push(x);
}
op.push(c);
break;
case '(':
op.push(c);
break;
case ')':
while(op.top()!='(')
{
Tree *r=stk.top(); stk.pop();
Tree *l=stk.top(); stk.pop();
Tree *x=new Tree('o',op.top(),0,l,r);
op.pop();
stk.push(x);
}
op.pop();
break;
default:
int num=0;
while(i<l&&exp[i]>='0'&&exp[i]<='9')
num=num*10+(exp[i++]-'0');
i-=1;
Tree *x=new Tree('n',0,num,0,0);
stk.push(x);
break;
}
}
while(!op.empty())
{
Tree *r=stk.top(); stk.pop();
Tree *l=stk.top(); stk.pop();
Tree *x=new Tree('o',op.top(),0,l,r);
op.pop();
stk.push(x);
}
A=stk.top(); stk.pop();
}
int Solve(Tree x)
{
if(x.type=='n')
return x.number;
switch(x.op)
{
case '+': return Solve(*x.left)+Solve(*x.right);
case '-': return Solve(*x.left)-Solve(*x.right);
case '*': return Solve(*x.left)*Solve(*x.right);
case '/': return Solve(*x.left)/Solve(*x.right);
}
return 0;
}
int main()
{
scanf("%s",exp);
l=strlen(exp);
ToTree();
printf("%d",Solve(*A));
return 0;
}