Cod sursa(job #2407444)

Utilizator puzzleFlutur Vasile puzzle Data 16 aprilie 2019 21:13:57
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.84 kb
#include <string>
#include <stack>
#include <fstream>

std::ifstream in("evaluare.in");
std::ofstream out("evaluare.out");

//stabileste prioritatea operatiei
int Priority(char x)
{
	if (x == '+' || x == '-')
		return 1;
	if (x == '*' || x == '/')
		return 2;
	//inseamna ca e ( sau )
	return 0;
}

//stabileste operatia propriu-zisa si o aplica
//pretty straight - forward
int ApplyOperator(int a, int b, char op)
{
	switch (op)
	{
		case '+': return a + b; 
		case '-': return a - b; 
		case '*': return a * b; 
		case '/': return a / b; 
	}
}

int Evaluate(std::string& Stream)
{
	int i;

	//aici stochez numerele propriu-zise
	std::stack<int> Valori;

	//aici stochez operatorii
	std::stack<char> Operatori;

	int n = Stream.length();

	for (i = 0; i < n; i++)
	{
		if (Stream[i] == '(')
		{
			Operatori.push(Stream[i]);
		}

		//daca este cifra, formez numarul si il introduc in coada.
		else if (isdigit(Stream[i]))
		{
			int numar = 0;

			while (i < Stream.length() && isdigit(Stream[i]))
			{
				numar = (numar * 10) + (Stream[i] - '0');
				i++;
			}
			i--;

			Valori.push(numar);
		}

		//in cazul in care intalnesc ')', trebuie sa rezolv intreaga paranteza
		else if (Stream[i] == ')')
		{
			//face asta pana ajung la final sau pana intalnesc inceputul parantezei
			while(!Operatori.empty() && Operatori.top() != '(')
			{ 
				int val2 = Valori.top();
				Valori.pop();

				int val1 = Valori.top();
				Valori.pop();

				char op = Operatori.top();
				Operatori.pop();

				Valori.push(ApplyOperator(val1, val2, op));
			}

			//scoate paranteza '('
			Operatori.pop();
		}

		else
		{
			//cat timp operatorii precedenti au prioritate mai mare sau egala decat operatorul curent
			//aplica operatorii respectivi inaintea celui curent
			//ex:
			//in cazul 2 + 3 + 6 * 2
			//aflandu-ma la ultimul operator, acesta va avea prioritatea 2, deci mai mare decat cei precedenti
			//astfel, operatorul curent va fi introdus in coada si va fi procesat la final sau la un pas urmator
			//respectandu-se astfel ordinea efectuarii operatiilor
			while (!Operatori.empty() && Priority(Operatori.top()) >= Priority(Stream[i]))
			{
				int val2 = Valori.top();
				Valori.pop();

				int val1 = Valori.top();
				Valori.pop();

				char op = Operatori.top();
				Operatori.pop();

				Valori.push(ApplyOperator(val1, val2, op));
			}

			Operatori.push(Stream[i]);
		}

	}

	while (!Operatori.empty())
	{
		//se executa operatiile ramase, putand fi executate liniar
		int val2 = Valori.top();
		Valori.pop();

		int val1 = Valori.top();
		Valori.pop();

		char op = Operatori.top();
		Operatori.pop();

		Valori.push(ApplyOperator(val1, val2, op));
	}

	return Valori.top();
}

int main()
{
	std::string Stream;
	in >> Stream;
	out << Evaluate(Stream);
}