Cod sursa(job #741005)

Utilizator ChallengeMurtaza Alexandru Challenge Data 25 aprilie 2012 08:58:17
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

const char InFile[]="evaluare.in";
const char OutFile[]="evaluare.out";
const int MaxN=100111;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Operator
{
	char op;
	int priority;
};

struct Token
{
	char type;
	int val;
};

char buffer[MaxN];
char *ptr=buffer;
stack<Operator> S;
stack<int> VS;
vector<Token> V;

inline void Pop()
{
	Token T;
	T.type=S.top().op;
	V.push_back(T);
	S.pop();
}

inline int Priority(char ch)
{
	if(ch=='(' || ch==')')
	{
		return 0;
	}
	if(ch=='+' || ch=='-')
	{
		return 1;
	}
	return 2;
}

inline bool valid(char ch)
{
	if(ch=='(' || ch==')' || ch=='+' || ch=='-' || ch=='*' || ch=='/')
	{
		return true;
	}
	return '0'<=ch && ch<='9';
}

inline int Atom(int a, int b, char type)
{
	if(type=='+')
	{
		return a+b;
	}
	if(type=='*')
	{
		return a*b;
	}
	if(type=='-')
	{
		return a-b;
	}
	return a/b;
}

int main()
{
	fin>>buffer;
	fin.close();
	
	while(*ptr)
	{
		if(!valid(*ptr))
		{
			++ptr;
			continue;
		}
		Operator O;
		if(*ptr=='(')
		{
			O.op='(';
			O.priority=Priority(O.op);
			S.push(O);
		}
		else if(*ptr==')')
		{
			while(S.top().op!='(')
			{
				Pop();
			}
			S.pop();
		}
		else if('0'<=*ptr && *ptr<='9')
		{
			int val=0;
			while('0'<=*ptr && *ptr<='9')
			{
				val*=10;
				val+=*ptr-'0';
				++ptr;
			}
			Token T;
			T.type='v';
			T.val=val;
			V.push_back(T);
			--ptr;
		}
		else
		{
			O.op=*ptr;
			O.priority=Priority(O.op);
			while(!S.empty())
			{
				if(S.top().priority<O.priority)
				{
					break;
				}
				Pop();
			}
			S.push(O);
		}
		++ptr;
	}
	while(!S.empty())
	{
		Pop();
	}
	
	for(vector<Token>::iterator it=V.begin();it!=V.end();++it)
	{
		if(it->type=='v')
		{
			VS.push(it->val);
		}
		else
		{
			int a=VS.top(); VS.pop();
			int b=VS.top(); VS.pop();
			VS.push(Atom(b,a,it->type));
		}
	}
	
	fout<<VS.top();
	fout.close();
	return 0;
}