Cod sursa(job #358059)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 21 octombrie 2009 19:37:54
Problema Evaluarea unei expresii Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 2.1 kb
#include<stdio.h>
#define infile "evaluare.in"
#define outfile "evaluare.out"
#define nmax (800*1001)
struct nod
{
	int val; //valoarea nodului
	char op; //operator
	int s,d; //pozitii pentru stanga si dreapta
} n[nmax]; //nodurile arborelui
char e[nmax]; //expresia
char *p=e; //pointer catre expresie
int nr; //valoarea ultimului nod folosit
int x; //radacina arborelui
int val; //valoarea expresiei

int expresie();
int termen();
int factor();

int expresie()
{
	int i,j;
	if(!(*p)) return 0;
	i=termen();
	if(*p=='+' || *p=='-' || *p=='*' || *p=='/') //daca nu s-a terminat expresia
	{
		j=++nr; //nod pentru operatorul dintre expresii
		n[j].op=*p,p++; //operatorul
		n[j].s=i; //expresia din partea stanga
		n[j].d=expresie(); //cealalta expresie
		i=j; //se schimba radacina expresiei
	}
	return i; //returnam radacina expresiei
}

int termen()
{
	int i,j;
	if(!(*p)) return 0;
	i=factor(); //termenul are cel putin un factor
	if(*p=='*' || *p=='/')
	{ //daca termenul mai are macar un factor
		j=++nr; //mai facem un nod pentru operatorul dintre cei doi factori
		n[j].op=*p,p++; //operatorul
		n[j].s=i; //partea stanga
		n[j].d=termen(); //partea dreapta poate fi tot un termen
		i=j; //se schimba radacina termenului
	}
	return i; //radacina termenului
}

int factor()
{
	int i;
	if(!(*p)) return 0;
	if(*p=='(')
	{ //daca avem o expresie
		p++;
		i=expresie();
		p++;
	}
	else
	{ //daca avem un factor simplu
		i=++nr;
		while(*p>='0'&&*p<='9') n[i].val=n[i].val*10+*p-'0',p++; //valoarea factorului
	}
	return i; //returnam radacina factorului
}

int eval(int x)
{
	switch(n[x].op)
	{
		case '+': return eval(n[x].s)+eval(n[x].d);
		case '-': return eval(n[x].s)-eval(n[x].d);
		case '*': return eval(n[x].s)*eval(n[x].d);
		case '/': return eval(n[x].s)/eval(n[x].d);
		default: return n[x].val;
	}
}

void read()
{
	fgets(e,nmax,stdin);
}

void init()
{
	x=expresie(); //construim arborele
}

void solve()
{
	val=eval(x); //calculam
}

void write()
{
	printf("%d\n",val);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	init();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}