Cod sursa(job #617592)

Utilizator ValidatorPopescu Vali Validator Data 15 octombrie 2011 05:45:37
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <fstream>
#include <cstring>
using namespace std;

ifstream f("evaluare.in");
ofstream g("evaluare.out");

char e[100001];//expresia
int S[100000]; //stiva numerelor
char op [100000]; //stiva operatorilor
int v1,v; //v-varful stivei S, v1-varful stivei op
int n;//nr de caractere din expresie

int numar(int &i)//construieste un numar incepand cu cifra de pe pozitia i
				// functia returneaza numaru si pozitia ultimei cifre din numar
	{
	int x=0;
	while(e[i]>='0'&& e[i]<='9'&&i<n)
	{
		x=x*10+(e[i]-'0');
		i++;
	}
	i--;
	return x;
	}

int calcul (int a, int b, char o) //efectueaza una din operatiile:+,-,*,/
	{
	switch (o)
		{
		case '+': a+=b; break;
		case '-': a-=b; break;
		case '*': a*=b; break;
		case '/': a/=b; break;
		}
	return a;
	}

int prioritate (char a)//stableste prioritatea operatorului a
						//+ si - au pr.1, * si /-au pr.2,iar (=pr.0
	{
	switch (a)
		{
		case '+':case '-': return 1;
		case '*':case '/': return 2;
		case '(': return 0;
		}
return 0;
	}

int main ()                             
	{
	int i;
	f.getline(e,100001);
	n = strlen(e);
	for(i=0;i<n;i++)//parcurgem caracterele expresiei
	{
	switch (e[i])
		{
		case '+':case '-':case '*':	case '/'://daca este +,-,*,/
			while(prioritate(op[v1])>=prioritate(e[i]))//prioritatea op. e[i]<=pr.op din vf. stivei
			    {//fac operatiile din varful stivei
					S[v-1]=calcul(S[v-1], S[v], op[v1]); v--; v1--;
				}
			     op[++v1]=e[i]; //adaug operatorul in stiva
				 break;

		case '(': op[++v1]=e[i];//adaug ( in stiva
			      break;
		case ')': while( op[v1]!='(')
				{//fac operatiile din varful stivei pana dau de )
				S[v-1]=calcul(S[v-1], S[v], op[v1]);
				v1--;v--;
				}
			    v1--;
			    break;
		default: S[++v]=numar(i);//daca am dat peste o cifra construiesc numarul si 
								//il pun in stiva

		}
	}
	while (v1)//cat tim stiva operatorilor mai contine ceva
		{
			S[v-1]=calcul(S[v-1], S[v], op[v1]);//calculez
			v1--; v--;
		}
	g<<S[1];
	f.close();
	g.close();
	return 0;

	}