Cod sursa(job #965169)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 23 iunie 2013 16:47:30
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.58 kb
#include <fstream>
#include <string.h>
#include <stack>
#define NMax 100000
#define LGElem 10000

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

char sir[NMax];

// converteste o expresie aritm. din infix in postfix
char* convToPostFix(char *sir);

// compara doi operatori aritmetici
int compOperatori(char x, char y);

// rezolva o expresie aritmetica in postfix
int rezolvaExp(char *sir);

int main()
{
	fin >> sir;
	fout << rezolvaExp(convToPostFix(sir));
	
	return 0;
}

// rezolva o expresie aritmetica in postfix
int rezolvaExp(char *sir)
{
	int i, aux, aux2, lgElem = 0, lg = strlen(sir);
	char elem[LGElem];
	stack<int> rez;

	elem[0] = NULL;
	for (i=0; i<lg; i++)
	{
		// nr pe poz curenta
		if ('0' <= sir[i] && sir[i] <= '9')
		{
			elem[lgElem++] = sir[i];
			elem[lgElem] = NULL;
		}
		else
		{
			// daca exista un element citit, il punem in stiva
			if (lgElem > 0)
			{
				aux = atoi(elem);
				rez.push(aux);

				lgElem = 0;
			}

			if (sir[i] == '+' || sir[i] == '-' || sir[i] == '*' || sir[i] == '/' && rez.size() >= 2)
			{
				aux = rez.top(), rez.pop();
				aux2 = rez.top(), rez.pop();

				switch (sir[i])
				{
					case '+': rez.push(aux+aux2); break;
					case '-': rez.push(aux2-aux); break;
					case '*': rez.push(aux*aux2); break;
					case '/': rez.push(aux2/aux); break;
				}
			}
		}
	}
	return rez.top();
}

char* convToPostFix(char *sir)
{
	int i, lgElem = 0, lgRez = 0, lg = strlen(sir);
	char elem[LGElem], rez[NMax], c;
	stack<char> op;

	elem[0] = NULL;
	rez[0] = NULL;
	for (i=0; i<lg; i++)
	{
		// nr pe poz curenta
		if ('0' <= sir[i] && sir[i] <= '9')
		{
			elem[lgElem++] = sir[i];
			elem[lgElem] = NULL;
		}
		else
		{
			// daca exista un element citit, il punem in sirul final
			if (lgElem > 0)
			{
				if (lgRez > 0)
				{
					strcat(rez, " ");
					lgRez++;
				}

				strcat(rez, elem);
				lgRez += lgElem;

				// nu mai avem nici un element acum
				lgElem = 0;
			}
			
			if (op.empty())
			{
				op.push(sir[i]);
			}
			else
			{
				// stiva nu este goala in acest moment
				c = op.top();

				if (sir[i] == ')')
				{
					while (!op.empty() && op.top() != '(')
					{
						c = op.top();
						op.pop();
						rez[lgRez++] = ' ';
						rez[lgRez++] = c;
						rez[lgRez] = NULL;
					}
					if (op.top() == '(')
					{
						op.pop();
					}
				}
				else
				{
					while (compOperatori(c, sir[i]) > 0)
					{
						op.pop();
						rez[lgRez++] = ' ';
						rez[lgRez++] = c;
						rez[lgRez] = NULL;

						if (op.empty())
						{
							break;
						}

						c = op.top();
					}
					op.push(sir[i]);
				}
			}
		}
	}

	if (lgElem > 0)
	{
		if (lgRez > 0)
		{
			strcat(rez, " ");
			lgRez++;
		}

		strcat(rez, elem);
		lgRez += lgElem;

		// nu mai avem nici un element acum
		lgElem = 0;
	}

	while (!op.empty())
	{
		c = op.top();
		rez[lgRez++] = ' ';
		rez[lgRez++] = c;
		rez[lgRez] = NULL;

		op.pop();
	}

	return rez;
}

/*
	compara doi operatori aritmetici
	-1 : x < y
	0 : x == y
	1 : x > y
*/
int compOperatori(char x, char y)
{
	if (x == '*' || x == '/')
	{
		if (y == '*' || y == '/')
		{
			return 0;
		}
		else
		{
			return 1;
		}
	}

	if (x == '+' || x == '-')
	{
		if (y == '+' || y == '-')
		{
			return 0;
		}
		
		if (y == '*' || y == '/')
		{
			return -1;
		}

		return 1;
	}
	 
	// stim sigur ca x este (
	if (y == '(')
	{
		return 0;
	}

	// stim clar ca y are prioritate mai mare fata de x
	return -1;
}