Cod sursa(job #2147623)

Utilizator AlexnolifeAlexandru Ica Alexnolife Data 28 februarie 2018 21:02:29
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 5.84 kb
#include <fstream>
#include <array>
#include <iostream>
#include <stack>
#include <vector>
#include <memory>
#include <list>

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

std::array<char, 100000> equation;

enum class MemberType : size_t
{
	NUMBER   = 0U, 
	OPERATOR = 1U, 
	NONE     = 2U
};

enum class OperatorType : size_t
{
	OPENEDPARANT = 0U, 
	CLOSEDPARANT = 0U, 
	PLUS = 1U, 
	MINUS = 1U, 
	TIMES = 2U, 
	DIVIDE = 2U, 
	NONE = 3U
};

class EqTerm
{
public:
	virtual size_t Value() const = 0; // verifica daca e numar, unul din "+-*/" sau o paranteza
	virtual int GetNumber() const = 0; // daca e numar pot sa ii iau valoarea
	virtual size_t GetOperatorType() const = 0; // daca face parte din "+-*/" atunci care din ele e mai exact
	virtual char GetCh() const = 0;
};

class Number : public EqTerm
{
private:
	int m_val;

public:
	Number() = default;
	Number(int num)
		: m_val(num)
	{}
	~Number() = default;

	virtual size_t Value() const final override
	{
		return static_cast<size_t>(MemberType::NUMBER);
	}

	virtual int GetNumber() const final override
	{
		return m_val;
	}

	virtual size_t GetOperatorType() const final override
	{
		return static_cast<size_t>(OperatorType::NONE);
	}

	virtual char GetCh() const final override
	{
		return '\0';
	}

};

class Operator : public EqTerm
{
private:
	char m_ch;

public:
	Operator() = default;
	Operator(char ch)
		: m_ch(ch)
	{}
	~Operator() = default;

	virtual size_t Value() const final override
	{
		return static_cast<size_t>(MemberType::OPERATOR);
	}

	virtual int GetNumber() const final override
	{
		return 0;
	}

	virtual size_t GetOperatorType() const final override
	{
		switch(m_ch) 
		{
		case '+': return static_cast<size_t>(OperatorType::PLUS);  
		case '-': return static_cast<size_t>(OperatorType::MINUS); 
		case '*': return static_cast<size_t>(OperatorType::TIMES); 
		case '/': return static_cast<size_t>(OperatorType::DIVIDE);
		case ')': return static_cast<size_t>(OperatorType::OPENEDPARANT);
		case '(': return static_cast<size_t>(OperatorType::CLOSEDPARANT);
		}

		return static_cast<size_t>(OperatorType::NONE);
	}
	
	virtual char GetCh() const final override
	{
		return m_ch;
	}

};

std::vector<std::unique_ptr<EqTerm>> rpn;
std::stack<std::unique_ptr<EqTerm>> rpnstack;
std::list<int> numbers;

void PushOnStack(char ch)
{
	if (rpnstack.empty()) {
		rpnstack.push(std::make_unique<Operator>(ch));
	}
	else if (ch != ')') {
		Operator elemtopush = Operator(ch);

		while (!rpnstack.empty() && 
			    elemtopush.GetOperatorType() < rpnstack.top()->GetOperatorType() &&
			    rpnstack.top()->GetOperatorType() != static_cast<size_t>(OperatorType::OPENEDPARANT))
		{
			rpn.emplace_back(std::make_unique<Operator>(rpnstack.top()->GetCh()));
			rpnstack.pop();
		}

		rpnstack.push(std::make_unique<Operator>(ch));
	}
	else {
		while (rpnstack.top()->GetOperatorType() != static_cast<size_t>(OperatorType::OPENEDPARANT)) {
			rpn.emplace_back(std::make_unique<Operator>(rpnstack.top()->GetCh()));
			rpnstack.pop();
		}

		rpnstack.pop();
	}
}

void Read()
{
	f >> equation.data();
}

void Solve()
{
	rpn.reserve(equation.size());

	size_t i;
	int currentNumber = 0;
	bool pendingNumber = false;
	bool byneg1 = false;

	for (i = 0; equation[i] != NULL; ++i) {
		char& ch = equation[i];

		switch (ch)
		{
		case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':case '0': {
			pendingNumber = true;
			currentNumber = currentNumber * 10 + static_cast<int>(ch - '0');

			if (byneg1) {
				currentNumber *= -1;
				byneg1 = false;
			}

			break;
		}
		case '-': {
			if (pendingNumber) {
				rpn.emplace_back(std::make_unique<Number>(currentNumber));

				pendingNumber = false;
				currentNumber = 0;
			}

			if (i == 0) {
				byneg1 = true;
			} 
			else if (equation[i - 1] == '(') {
				byneg1 = true;
			}
			else {
				byneg1 = false;
				PushOnStack(ch);
			}

			break;
		}
		case '+':case '*':case '/':case '(':case ')': {
			if (pendingNumber) {
				rpn.emplace_back(std::make_unique<Number>(currentNumber));

				pendingNumber = false;
				currentNumber = 0;
			}

			PushOnStack(ch);

			break;
		}
		}
	}

	if (currentNumber) {
		rpn.emplace_back(std::make_unique<Number>(currentNumber));
	}

	while (!rpnstack.empty()) {
		rpn.emplace_back(std::make_unique<Operator>(rpnstack.top()->GetCh()));
		rpnstack.pop();
	}
}

int main(int argc, char ** argv)
{
	Read();
	Solve();

	auto left  = numbers.begin();
	auto right = numbers.begin();

	for (int i = 0; i < rpn.size(); ++i) {
		if (rpn[i]->Value() == static_cast<size_t>(MemberType::NUMBER)) {
			numbers.emplace_back(rpn[i]->GetNumber());
		}
		else {
			left  = numbers.end();
			right = numbers.end();
	
			if (numbers.size() >= 2) {
				left--;
				left--;
				right--;
			}
			else if (numbers.size() == 1) {
				left = --right;
			}
			else {
				break;
			}

			switch (rpn[i]->GetCh())
			{
			case '+': {
				int result = (*left) + (*right);

				numbers.pop_back();
				numbers.pop_back();

				numbers.emplace_back(result);

				break;
			}
			case '-': {
				int result = (*left) - (*right);

				numbers.pop_back();
				numbers.pop_back();

				numbers.emplace_back(result);

				break;
			}
			case '*': {
				int result = (*left) * (*right);

				numbers.pop_back();
				numbers.pop_back();

				numbers.emplace_back(result);

				break;
			}
			case '/': {
				int result = (*left) / (*right);

				numbers.pop_back();
				numbers.pop_back();

				numbers.emplace_back(result);

				break;
			}
			default: {
				numbers.emplace_back(*left);
				
				break;
			}
			}
		}
	}

	if (!numbers.empty()) {
		g << numbers.back() << "\n";
	}

	return 0;
}