Cod sursa(job #456546)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define inf "evaluare.in"
#define outf "evaluare.out"
#define LMax 100100
#define INF 0x3f3f3f3f
using namespace std;
int k,n;
int p[LMax],pfp[LMax];
char efp[LMax][20];
char e[LMax][20];
char sir[LMax];
char fp[LMax][20];
int t;
int st[LMax];
struct Nod
{
char op[20];
Nod *as,*ad;
};
Nod *v;
void read()
{
scanf("%s",sir+1);
for(int i=1; i<=strlen(sir+1); i++ )
if( (int)(sir[i])>=(int)('0') && (int)(sir[i])<=(int)('9') )
{
k++;
e[k][0] = sir[i];
int j=i+1;
while( (int)(sir[j])>=(int)('0') && (int)(sir[j])<=(int)('9') ) e[k][ strlen(e[k]) ] = sir[j] , j++ ;
j--;
i = j;
}
else
{
k++;
e[k][0] = sir[i];
}
}
Nod* arb(int li,int ls)
{
int poz,min;
min = pfp[ls];
poz=ls;
for(int i=ls-1; i>=li; i-- )
if( pfp[i]<min )
{
min=pfp[i];
poz=i;
}
Nod *c=new Nod;
strcpy( c->op, efp[poz] );
if( li==ls ) c->as = c->ad = 0;
else
{
c->as = arb(li,poz-1);
c->ad = arb(poz+1,ls);
}
return c;
}
void SDV(Nod *s)
{
if( s )
{
SDV( s->as );
SDV( s->ad );
strcpy( fp[++t], s->op );
}
}
void solve()
{
int j=0;
for(int i=1; i<=k; i++)
switch( e[i][0] )
{
case ')' : j-=10 ; break;
case '(' : j+=10 ; break;
case '+' : p[i]=1+j; break;
case '-' : p[i]=1+j; break;
case '*' : p[i]=10+j; break;
case '/' : p[i]=10+j; break;
default : p[i]=INF;
}
for(int i=1; i<=k; i++)
if( e[i][0]!='(' && e[i][0]!=')' )
{
n++;
strcpy( efp[n], e[i] );
pfp[n] = p[i];
}
v = arb(1,n);
SDV(v);
t=0;
int rez;
for(int i=1; i<=n; i++)
if( fp[i][0]=='+' || fp[i][0]=='-' || fp[i][0]=='*' || fp[i][0]=='/' )
{
switch( fp[i][0] )
{
case '+' : rez = st[t]+st[t-1]; break;
case '-' : rez = st[t]-st[t-1]; break;
case '*' : rez = st[t]*st[t-1]; break;
case '/' : rez = st[t-1]/st[t]; break;
}
t--;
st[t]=rez;
}
else t++, st[t] = atol( fp[i] );
printf("%d",st[1]);
//for(int i=1; i<=n; i++) printf("%s ",fp[i]);
}
int main()
{
freopen(inf,"r",stdin);
freopen(outf,"w",stdout);
read();
solve();
return 0;
}