Cod sursa(job #348160)

Utilizator prdianaProdan Diana prdiana Data 14 septembrie 2009 18:18:44
Problema Evaluarea unei expresii Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
#include <stdio.h>
#include <stack>
#define MAXN 100002

using namespace std;

int pred(char oper)
{
	switch (oper)
	{
	case '+':
		return 1;
	case '-':
		return 2;
	case '/':
		return 3;
	case '*':
		return 3;
	}
}

struct term
{
	int val;
	char oper;
	bool number;
};



term parse(term *a,int size,int &cj)
{
	int i = 1;
	stack<term> s;
	stack<char> op;
	term aux;
	bool pnext = false;
	char pnextop;
	int oj =0,yy =0;
	for (i=1;i<=size;i++)
	{
		oj++;
		if (a[i].oper == '(')
		{
			s.push(parse(a+i,size-i,yy));
			if (pnext)
			{
				aux.number = false;
				aux.oper = pnextop;
				s.push(aux);
				pnext = false;
			}

			i+=yy;
		}
		else if (a[i].number)
		{
			aux.number = true;
			aux.val = a[i].val;
			s.push(aux);
			if (pnext)
			{
				aux.number = false;
				aux.oper = pnextop;
				s.push(aux);
				pnext = false;
			}
		}
		else if (a[i].oper != ')')
		{
			if (!op.empty())
			{
					if (pred(op.top())>pred(a[i].oper))
					{
						aux.number = false;
						aux.oper = op.top();
						s.push(aux);
						op.pop();
					}
					op.push(a[i].oper);
			}
			else
			{
				op.push(a[i].oper);
			}
		}
		else if (a[i].oper == ')')
		{
			break;
		}
	}
	cj = oj+yy;
	stack<char> op2;
	while (!op.empty())
	{
		aux.number = false;
		aux.oper = op.top();
		s.push(aux);
		op.pop();
	}

	while (!op2.empty())
	{
		aux.number = false;
		aux.oper = op2.top();
		s.push(aux);
		op2.pop();
	}
	
	stack<term> s2;
	while (!s.empty())
	{
		s2.push(s.top());
		s.pop();
	}
	stack<int> eval;
	int t1,t2;
	t1 =0;

	while (!s2.empty())
	{
		if (s2.top().number)
		{
			eval.push(s2.top().val);
		}
		else
		{
			switch (s2.top().oper)
			{
			case '+':
				t1 = eval.top();
				eval.pop();
				t2 = eval.top();
				eval.pop();
				eval.push(t1+t2);
				break;
			case '-':
				t1 = eval.top();
				eval.pop();
				t2 = eval.top();
				eval.pop();
				eval.push(t2-t1);
				break;
			case '*':
				t1 = eval.top();
				eval.pop();
				t2 = eval.top();
				eval.pop();
				eval.push(t1*t2);
				break;
			case '/':
				 t1 = eval.top();
				eval.pop();
				t2 = eval.top();
				eval.pop();
				eval.push(t2/t1);
				break;
			}
		}
		s2.pop();
	}
	aux.number = true;

	aux.val = eval.top();
	return aux;
}

int main()
{
	term *a;
	a = new term[MAXN];
	freopen("evaluare.in","r",stdin);
	freopen("evaluare.out","w",stdout);
	char aux;
	int size = 0,nr;

	while (!feof(stdin))
	{
		scanf("%c",&aux);
		if (aux != '\n')
		{
			if (aux >= '0' && aux <= '9')
			{
				nr = 0;
				while (aux >= '0' && aux <= '9' && !feof(stdin))
				{
					nr*=10;
					nr+=aux - '0';
					scanf("%c",&aux);
				}
				size++;
				a[size].number = true;
				a[size].val = nr;
			}
		}
		if (aux != '\n' && !feof(stdin))
		{
			size++;
			a[size].number = false;
			a[size].oper = aux;
		}
	}
	
	term rez;
	int useless;
	rez = parse(a,size,useless);
	printf("%d",rez.val);
	return 0;
}