Cod sursa(job #727504)

Utilizator m_mihai92Mocanu Mihai m_mihai92 Data 28 martie 2012 00:23:39
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.28 kb
#include <iostream>
#include <fstream>

using namespace std;

int const dimMax=100000;

bool is_op(char c)
{
	if ((c=='+')||(c=='-')||(c=='*')||(c=='/')||(c=='(')||(c==')'))
		return true;
	else
		return false;
};
bool is_num(char c)
{
	if ((c<='9')&&(c>='0'))
		return true;
	else
		return false;
}

int priority (char c)
{
	switch (c)
	{
    case '*':  case '/':
        return 2;
    case '+': case '-':
        return 1;
	}
	return 0;
}

void shunting_yard(char *p, char q[dimMax][10])
{
	int k=-1,contor,j=0;
	char *i=p;
	char stack[dimMax], num[10];

	while (is_num(*i)||is_op(*i))
	{
		if(is_op(*i))
		{
			//daca am intalnit o paranteza inchisa
			if (*i==')')
			{
				//scoatem din stiva de operatori tot pana la cea deschisa
				while ((stack[k]!='(')&&(k>=0))
					q[j++][0]=stack[k--];
				//apoi o eliminam pe cea deschisa
				k--;
			}
			else
			{
				//daca avem orice inafara de paranteza deschisa
				if(*i!='(')
				{
					//scoatem din stiva de operatori tot ce are prioritate >
					//sau = cu operatorul curent
					while ((priority(*i)<=priority(stack[k])) && (k>=0))
						q[j++][0]=stack[k--];
				}
				stack[++k]=*i;
			}
			++i;
		}
		else
		{
			contor=0;
			while (is_num(*i))
			{
				q[j][contor++]=*i;
				++i;
			}
			++j;
			q[j][contor]='\0';
		}
	}

	while(k>=0)
		q[j++][0]=stack[k--];
	q[j][0]='\0';
}
int atoi(char a[10])
{
	int i=0, x=0;
	while (a[i] >= '0' && a[i] <= '9' )
	{
		x = x * 10 + a[i] - '0';
		++i;
	}
	return x;
}
int evaluate(char q[dimMax][10])
{
	int r[dimMax];
	int i=0,j=0;
	while (q[i][0]!='\0')
	{
		if(is_num(q[i][0]))
			//push in stiva
			r[j++]=atoi(q[i]);
		else
		{
			j=j-1;
			switch (q[i][0])
				{
			    case '*':
			    	r[j-1] *=r[j];
			    	break;
			    case '/':
			    	r[j-1] /= r[j];
			    	break;
			    case '+':
			    	r[j-1] +=r[j];
			    	break;
			    case '-':
			    	r[j-1] -=r[j];
			    	break;
				}
		}
		++i;
	}
	return r[0];
}

int main ()
{

	char *exp, rpn[dimMax][10];
	fstream f("evaluare.in", ios::in), g("evaluare.out", ios::out);
	exp= new char [dimMax];

	f.getline(exp,dimMax);
	f.close();
	shunting_yard(exp,rpn);

	g<<evaluate(rpn);
	g.close();
	delete [] exp;

	return 0;
}