Cod sursa(job #597874)

Utilizator Brz_VladBrezae Vlad Brz_Vlad Data 23 iunie 2011 19:16:02
Problema Evaluarea unei expresii Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.24 kb
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

enum type{ERR,OPERATOR,PARANTEZA,OPERAND};

struct next{
	type tip;
	int val;
};

struct Stack{
	next tip;
	Stack* back;
};

void InitS(Stack &s)
{
	s.back=NULL;
}

void PushS(Stack &s,next tip)
{
	Stack* nou = new Stack;
	nou->tip = tip;
	nou->back = s.back;
	s.back = nou;
}

next TopS(Stack s)
{
	if(s.back != NULL)
		return s.back->tip;
	else{
		next err;
		err.tip = ERR;
		return err;
	}
}

next PopS(Stack &s)
{
	if(s.back == NULL){
		next err;
		err.tip = ERR;
		return err;
	}
	else{
		next ret;
		Stack* pt;
		ret = s.back->tip;
		pt = s.back;
		s.back = s.back->back;
		delete pt;
		return ret;
	}
}

int Prioritate(next op)
{
	if(op.tip = ERR)
		return -1;
	else if(op.val == '+' || op.val == '-')
		return 1;
	else
		return 2;
}

next calc(next x1,next x2,next op)
{
	next ret;
	ret.tip = OPERAND;
	switch(op.val){
		case '+': ret.val = x1.val+x2.val; break;
		case '-': ret.val = x1.val-x2.val; break;
		case '*': ret.val = x1.val*x2.val; break;
		case '/': ret.val = x1.val/x2.val; break;
		default : ret.tip = ERR;
				  return ret;
	}
	return ret;
}

next Extrage(char *&sir)
{
	next obiect;
	char* aux = new char[11];
	char* ini = aux;
	while(*sir==' ')
		sir++;
	switch(*sir){
		case ')':
		case '(':	obiect.tip = PARANTEZA;
					obiect.val = *sir;
					sir++;
					break;
		case '+':
		case '-':
		case '/':
		case '*':   obiect.tip = OPERATOR;
					obiect.val = *sir;
					sir++;
					break;
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':	while(isdigit(*sir)){
						*aux = *sir;
						aux++;
						sir++;
					}
					*aux = 0;
					obiect.tip = OPERAND;
					obiect.val = atoi(ini);
					break;
		default : obiect.tip = ERR;
	}
	
	delete ini;
	return obiect;
}

next EvalueazaPartial(Stack &stOperatori,Stack &stOperanzi,bool popp)
{
	next ret;
	ret.tip = OPERAND;
	next t1,t2,op;
	while((op=PopS(stOperatori)).tip != PARANTEZA && op.tip!=ERR){
		t2 = PopS(stOperanzi);
		t1 = PopS(stOperanzi);
		ret = calc(t1,t2,op);
		PushS(stOperanzi,ret);
	}
	
	if(!popp)
		if(op.tip == PARANTEZA){
			next aux;
			aux.tip = PARANTEZA;
			aux.val = '(';
			PushS(stOperatori,aux);
		}

	return ret;
}


int main(int argc, char* argv[])
{
	FILE *fpr,*fpw;
	char *sir;
	sir = new char[100000];
	fpr = fopen("evaluare.in","r");
	fpw = fopen("evaluare.out","w");

	Stack stOperatori;
	Stack stOperanzi;
	InitS(stOperatori);
	InitS(stOperanzi);
	
	next cur;

	fgets(sir,100000,fpr);

	while((cur=Extrage(sir)).tip != ERR){
		switch(cur.tip){
			case OPERAND:  PushS(stOperanzi,cur);
							break;
			case OPERATOR:	if( Prioritate(cur) < Prioritate(TopS(stOperatori)))
							   EvalueazaPartial(stOperatori,stOperanzi,false);
							PushS(stOperatori,cur);
							break;
			case PARANTEZA: if(cur.val == '(')
								PushS(stOperatori,cur);
							else
								EvalueazaPartial(stOperatori,stOperanzi,true);
							break;
		}	
	}
	EvalueazaPartial(stOperatori,stOperanzi,true);
	next rezultat = PopS(stOperanzi);

	fprintf(fpw,"%d",rezultat.val);

	fclose(fpr);
	fclose(fpw);
	return 0;
}