Cod sursa(job #677525)

Utilizator alecsandrualex cuturela alecsandru Data 10 februarie 2012 12:20:20
Problema Evaluarea unei expresii Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 3.03 kb
#include<stdio.h>
#include<stack>
using namespace std;
#define PD 1000000001
#define MIN 1000000002
#define PLUS 1000000003
#define ORI 1000000004
#define DIV 1000000005
char s[100000];
stack <int> op;
stack <int> polo;
int val,i,nr,oper,g,p[100000],val2;
int ct,aa,bb,start,pb,pa,ca;
int main()
{
	freopen("evaluare.in","r",stdin);
	freopen("evaluare.out","w",stdout);
	gets(s);
	for(i=0;s[i]!=0;i++)
	{
		if('0'<=s[i]&&s[i]<='9')
		{
			nr=s[i]-'0';
			while('0'<=s[i+1]&&s[i+1]<='9')
			{
				i++;
				nr=nr*10+s[i]-'0';
			}
			if(!polo.empty()&&op.top()==MIN)
			{nr=nr-2*nr;	
			polo.push(nr);
			op.pop();
			}
			else
				polo.push(nr);
		}
		if(s[i]=='(')
		{
			op.push(PD);
		}
		if(s[i]=='-'||s[i]=='+')
		{
			if(s[i]=='-')
				oper=MIN;
			else
				oper=PLUS;
			if(op.empty())
			{
				op.push(oper);
			}
			else
			{	if(op.top()==PD)	
				{
					op.push(oper);
				}
				else
				{
					while(!op.empty())
					{
						if(op.top()!=PD)
						{g=op.top();
						polo.push(g);
						op.pop();}
						else
							break;
					}
					op.push(oper);
				}
			}
		}
		if(s[i]=='*'||s[i]=='/')
		{
			if(s[i]=='*')
				oper=ORI;
			else
				oper=DIV;
			if(op.empty())
			{	
				op.push(oper);
			}
			else
			{
				if(op.top()==PD||op.top()==MIN||op.top()==PLUS)
				{
					op.push(oper);
				}
				else
				{
					while(!op.empty()||op.top()!=PD||op.top()!=MIN||op.top()!=PLUS)
					{
						g=op.top();
						polo.push(g);
						op.pop();
					}
					op.push(oper);
				}
			}
		}
		if(s[i]==')')
		{
			while(op.top()!=PD)
			{
				g=op.top();
				polo.push(g);
				op.pop();
			}
			op.pop();
		}
	}
	while(!op.empty())
	{
		g=op.top();
		polo.push(g);
		op.pop();
	}
	val2=polo.size();
	val=val2;
	while(!polo.empty())
	{
		g=polo.top();
		p[val2]=g;
		val2--;
		
		polo.pop();
	}
	/*for(i=1;i<=val;i++)
	{
		g=p[i];
		if(g<1000000000)
		{
			printf("%d",g);
		}
		if(g==MIN)
			printf("-");
		if(g==PLUS)
			printf("+");
		if(g==ORI)
			printf("*");
		if(g==DIV)
			printf("/");
		printf(" ");
	}*/
	for(i=1;i<=val;i++)
		ct=0;
	for(i=1;i<=val;i++)
	{
		if(p[i]>1000000001&&p[i]!=1000000007)
		{
			
				ct=0;
				start=i-1;
				aa=bb=0;
				pa=pb=0;
				ca=0;
				while(!ct)
				{
					if(ca==0&&p[start]<1000000000)
					{aa=p[start]; pa=start; ca=1;}
					else
					if(ca!=0&&p[start]<1000000000)
					{
						bb=p[start];
						pb=start;
						ct=1;
					}
					start--;
				}
			g=p[i];
			if(g==1000000002)
			{	p[i]=bb-aa;
				p[pa]=1000000007;
				p[pb]=1000000007;
			}
			if(g==1000000003)
			{	p[i]=aa+bb;
				p[pa]=1000000007;
				p[pb]=1000000007;
			}
			if(g==1000000004)
			{	p[i]=aa*bb;
				p[pa]=1000000007;
				p[pb]=1000000007;
			}
			if(g==1000000005)
			{	
				if(aa==0)
				{	p[val]=999999; i=val+1; }
				else
				{p[i]=bb/aa;
				p[pa]=1000000007;
				p[pb]=1000000007;
				}
			}
		}
	}
	for(i=1;i<=val;i++)
		ct=0;
	g=p[val];
	printf("%d",g);
	return 0;
}