Cod sursa(job #194597)

Utilizator cipPaduraru Ciprian - Ionut cip Data 12 iunie 2008 11:16:45
Problema Evaluarea unei expresii Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define IN "evaluare.in"
#define OUT "evaluare.out"
#define MAXN 100001

char lg[MAXN];
int length;
class Node
{	public:

	char type;	//n, + - 
	int info;	//number
	Node *st,*dr;
	
};
bool isdigit(char c) {return (c>='0' && c<='9');}
int ExtrageNumar(int &i)
{
	int nr = 0;
	while(isdigit(lg[i]))
		nr=nr * 10 + (lg[i++] - '0');
	return nr;
}


Node *CreeazaArbore(int &i);
Node *MakeTermen(int &i);
Node *MakeFactor(int &i)
{
	Node *p = NULL;
	if (lg[i] == '(')
	{
		++i;
		p=CreeazaArbore(i);
		i++;
		return p;
	}
	p = new Node;

	int nr;
	bool number = false;
	if (isdigit(lg[i]))
	{
		number = true;
		nr = ExtrageNumar(i);
		p->type='n';
	}
	else
		p->type = lg[i];

	p->info = ( number == false ? lg[i++] : nr);
	p->st = p->dr = NULL;
	return p;
}

Node *MakeTermen(int &i)
{
	Node *p = NULL,*r = NULL;
	r = MakeFactor(i);
	if (i >= length || (lg[i]!='*' && lg[i]!='/'))
		return r;

	p = new Node();
	p->type =lg[i];
	p->info = lg[i++];
	p->st = r;
	p->dr = MakeTermen(i);
	return p;
}

Node *CreeazaArbore(int &i)
{
	if (i >= length) return NULL;
	Node *r=MakeTermen(i);
	if (i >= length || lg[i] == ')')
		return r;

	Node *p = new Node();
	p->type = lg[i];
	p->info = lg[i++];
	p->st = r;
	p->dr = CreeazaArbore(i);
	return p;
}

void read()
{
	FILE *f=fopen(IN,"r");
	fscanf(f,"%s",&lg);
	length = strlen(lg);
	fclose(f);
}

int Evaluate(Node *rad)
{
	if (rad == NULL)
		return 1;
	else
	{
		switch(rad->type)
		{
			case '+':
				return (Evaluate(rad->st) + Evaluate(rad->dr));
				break;
			case '-':
				return (Evaluate(rad->st) - Evaluate(rad->dr));
				break;
			case '*':
				return (Evaluate(rad->st) * Evaluate(rad->dr));
				break;
			case '/':
				return (Evaluate(rad->st) / Evaluate(rad->dr));
				break;
			default:
				return rad->info;
		}
	}
}

int main()
{
	read();
	int v=0;
	Node *radacina = CreeazaArbore(v);

	FILE *f=fopen(OUT,"w");
	fprintf(f,"%d\n",Evaluate(radacina));
	fclose(f);

	return 0;
}