Cod sursa(job #1214217)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 29 iulie 2014 20:05:43
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 3.11 kb
#include <cstdio>
using namespace std;
class Stack
{
private:
	char s[50000];
	int top;
public:
	Stack(){};
	Stack(int newTop):top(newTop){}
	void pop() {--top;}
	void push(char c)
	{
		++top;
		this->s[top]=c;
	}
	bool isEmpty()
	{
		if(top>0) return 0;
		return 1;
	}
	char Top() { return s[top]; }
	void emptyStack() { top=0; }
};

typedef struct nod
{
	nod *left,*right;
	char op;
	long val;
	nod(long _val=0,char _op=' '):val(_val),op(_op){};
}NOD;

typedef struct{nod* v[100001];int top;} NodeStack;

bool isOperator(char c)
{
	return (c=='+' || c=='-' || c=='*' || c=='/');
}

int priority(char c)
{
	int pri=0;
	if(c=='+' || c=='-') pri=1;
	else if(c=='*' || c=='/') pri=2;
	return pri;
}

NOD* pop(NodeStack &s) { NOD * n=s.v[s.top];--s.top; return n;}

void push(NodeStack &s,NOD *p) { s.v[++s.top]=p;}

long calculus(long a,long b,char c)
{
	switch(c)
	{
		case '+': return a+b;
		case '-':return a-b;
		case '*':return a*b;
		case '/':return a/b;
	}
}

long st[100002],m;
void evaluate(NOD *root)
{
	long calc;
	if(root!=NULL)
	{
		evaluate(root->left);
		evaluate(root->right);
		if(root->val!=0) st[++m]=root->val;
		else
		{
			long a,b;
			a=st[m];--m;
			b=st[m];--m;
			calc=calculus(b,a,root->op);
			st[++m]=calc;
		}
	}
}
int main()
{
	FILE *f,*g;
	f=fopen("evaluare.in","r");
	g=fopen("evaluare.out","w");
	char s[100003],postfix[200009],p=0;
	int i,length,neg;
	long rez=0,nr=0;
	length=fread(s,sizeof(char),100003,f);
	Stack stack(0);
	for(i=0;i<length;++i)
	{
		if(s[i]>='0' && s[i]<='9')
		{
			if(s[i-1]=='-') postfix[p++]=s[i-1];
			postfix[p++]=s[i];
			while(s[i+1]>='0' && s[i+1]<='9')
			{
				++i;
				postfix[p++]=s[i];
			}
			postfix[p++]=' ';
		}
		else if(s[i]=='(') stack.push(s[i]);
		else if(s[i]==')')
		{
			while(stack.Top()!='(')
			{
				postfix[p++]=stack.Top();
				postfix[p++]=' ';
				stack.pop();
			}
			stack.pop();
		}
		else if(isOperator(s[i]))
		{
			if(stack.isEmpty())
			{
				stack.push(s[i]);
			}
			else
			{
				while(priority(stack.Top())>=priority(s[i]))
				{
					postfix[p++]=stack.Top();
					postfix[p++]=' ';
					stack.pop();
				}
				stack.push(s[i]);
			}
		}
	}
	while(!stack.isEmpty()) {postfix[p++]=stack.Top();postfix[p++]=' ';stack.pop();}
	postfix[p]='\0';
	NodeStack nstack;
	nstack.top=0;
	for(i=0;i<p;++i)
	{
		if(postfix[i]>='0' && postfix[i]<='9')
		{
			if(i-1>=0 && postfix[i-1]=='-') neg=1;
			while(postfix[i]!=' ')
			{
				nr=nr*10+postfix[i]-'0';
				++i;
			}
			if(neg==1) nr=nr*(-1);
			NOD *newN=new nod;
			newN->left=NULL;
			newN->right=NULL;
			newN->val=nr;
			push(nstack,newN);
			nr=0;
			neg=0;
		}
		else if(isOperator(postfix[i]) &&!(postfix[i]=='-' && postfix[i+1]>='0' && postfix[i+1]<='9'))
		{
			NOD *op1,*op2;
			op1=pop(nstack);
			op2=pop(nstack);
			NOD *newN=new nod;
			newN->left=op2;
			newN->right=op1;
			newN->op=postfix[i];
			push(nstack,newN);
		}
	}
	NOD *root=pop(nstack);
	stack.emptyStack();
	evaluate(root);
	fprintf(g,"%ld",st[m]);
	fclose(f);
	fclose(g);
	return 0;
}