Cod sursa(job #2215516)

Utilizator NarniaDavid Popescu Ioan Narnia Data 22 iunie 2018 14:17:52
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
#include <string>
#include <stack>
#include <fstream>

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

bool is_operator(char a)
{
	return (a == '+' || a == '-' || a == '^' || a == '*' || a == '/' || a == '(' || a == ')');
}

bool is_operand(char a)
{
	return ((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z'));
}

int precedence(char a)
{
	if (a == '^')
		return 3;
	if (a == '*' || a == '/')
		return 2;
	if (a == '+' || a == '-')
		return 1;
	return 0;
}

std::string getNext(std::string expr, int &i)
{
	std::string rezult;
	if (is_operator(expr[i]))
		return (rezult+expr[i]);
	while (i<expr.length() && !is_operator(expr[i]))
		rezult+=expr[i++];
	rezult+=' ';
	--i;
	return rezult;
}

std::string infix_to_postfix(std::string expr)
{
	int i;
	std::string rezult;
	std::stack <std::string> operand_stack;
	operand_stack.push("X");
	std::string current;
	for (i= 0; i<expr.length(); i++)
	{	
		current = getNext(expr, i);
		if (current.length()!=1)
		{
			rezult+=current;
		}
		else if (current[0] == '(')
		{
			operand_stack.push("(");
		}
		else if (current[0] == ')')
		{
			while (operand_stack.top() != "(" && operand_stack.top() != "X")
			{
				rezult += operand_stack.top();
				operand_stack.pop();
			}
			if (operand_stack.top() == "(")
				operand_stack.pop();
		}
		else
		{
			while (operand_stack.top() != "X" && precedence(expr[i]) <= precedence(operand_stack.top()[0]))
			{
				rezult+=operand_stack.top();
				operand_stack.pop();
			}		
			std::string aux = "";
			aux+=expr[i];
			operand_stack.push(aux);
		}
	}
	while (operand_stack.top() != "X")
	{
		rezult+=operand_stack.top();
		operand_stack.pop();
	}
	return rezult;
}





std::string postfix_getNext(std::string expr, int &i)
{
	std::string rezult;
	if (is_operator(expr[i]))
		return (rezult+expr[i]);
	while (i<expr.length() && (expr[i]!=' '))
		rezult+=expr[i++];
	return rezult;
}


int interpret(int termen1, int termen2, char operand)
{
	switch(operand)
	{
		case '+': return termen1+termen2;
		case '-': return termen2-termen1;
		case '*': return termen1*termen2;
		case '/': return termen2/termen1;
	}
}

int eval_expr(std::string expr)
{
	std::stack <int> st;
	int t1, t2, rezult;
	std::string current;
	for (int i =0;i<expr.length();i++)
	{
		current = postfix_getNext(expr, i);
		if (!is_operator(current[0]))
			{
				st.push(std::stoi(current));
			}
		else
			{
				t1 = st.top();
				st.pop();
				t2 = st.top();
				st.pop();
				rezult = interpret(t1, t2, expr[i]);
				st.push(rezult);
			}
	}
	return st.top();
}


int main()
{
	std::string expression;
	std::string result;
	f>>expression;
	result = infix_to_postfix(expression);;
	g<<eval_expr(result)<<"\n";
	return (0);
}