Cod sursa(job #148655)

Utilizator razvan2006razvan brezulianu razvan2006 Data 4 martie 2008 17:40:00
Problema Evaluarea unei expresii Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.96 kb
#include<stdio.h>
#include <string.h>
#include<stdlib.h>

typedef struct nod
{
	char v;
	/*
	v poate fi +, -, *, / sau c
	c - constanta a carei valoare o retin in val
	*/
	int val;

	nod * st, * dr;
}nod;

int i, j, n, ok, valoare;
char s[100001];
nod *rad;
FILE *fin, *fout;

void evalueaza(nod * a)
{
	if(a->st)
	{
		evalueaza(a->st);
		evalueaza(a->dr);
	}

	if(a->v == 'n')
		return ;
	else
	{
		if(a->v == '+')
			a->val = a->st->val + a->dr->val;	
	
		if(a->v == '-')
			a->val = a->st->val - a->dr->val;	
		
		if(a->v == '*')
			a->val = a->st->val * a->dr->val;	
	
		if(a->v == '/')
			a->val = a->st->val / a->dr->val;	
	}
}

nod * completeaza(int ps, int pf)
{
	int poz;
	nod *tmp;

	if (ps > pf)
	{
		tmp = (nod *) malloc(sizeof(nod));
		tmp -> v = 'n';
		tmp -> val = 0;
		tmp -> st = NULL;
		tmp -> dr = NULL;
	}
	else
	{
 		if(s[ps] == '(' && s[pf] == ')')
			return completeaza(++ps, --pf);
		else
		{
			poz = -1;
			ok = 0;

			for(i = ps; i <= pf; i++)
			{
				if(ok == 0 && poz == -1 && (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/'))
					poz = i;
				if(ok == 0 && (s[i] == '+' || s[i] == '-'))
					poz = i;

				if(s[i] == '(')
					ok++;
				if(s[i] == ')')
					ok--;
			}


			if(poz == -1)
			{
				valoare = 0;

				for(i = ps; i <= pf; i++)
					valoare = valoare * 10 + s[i] - '0';


				tmp = (nod *) malloc(sizeof(nod));
				tmp -> v = 'n';
				tmp -> val = valoare;
				tmp -> st = NULL;
				tmp -> dr = NULL;
			}
			else
			{
				tmp = (nod *)malloc(sizeof(nod));
				tmp -> v = s[poz];
				tmp -> val = 0;
				tmp -> st = completeaza(ps, poz - 1);
				tmp -> dr = completeaza(poz + 1, pf);
			}
		}
	}
	return tmp;
}

int main()
{
	fin = fopen("evaluare.in", "rt");
	fout = fopen("evaluare.out", "wt");

	fscanf(fin, "%s", &s);

	rad = completeaza(0, strlen(s) - 1);

	evalueaza(rad);
	fprintf(fout, "%d\n", rad->val);

	return 0;
}