Cod sursa(job #1839373)

Utilizator ArkinyStoica Alex Arkiny Data 2 ianuarie 2017 20:37:53
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.24 kb
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;


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

char expr[100010];

#define INCORRECT_EXPRESSION 1;

class Expression_evaluator
{
private:
	char expr[200010];
	vector<int> polish_expr;
	vector<int> stk;

	int it;
	
	const char Expresion_symbols[8] = { 0,'*','/','+','-','(',')'};

	const int Priority_symbols[8] = { 0,4,4,3,3,2,1};
	
	int parse_number(char s[])
	{
		int nr = 0;
		int ok = 0;
		while (s[it] >= '0' && s[it] <= '9')
		{
			nr = nr * 10 + (s[it] - '0');
			++it;
			ok = 1;
		}
		if (ok)
			return nr;
		else
		{
			for(int i=1;i<=6;++i)
				if (s[it] == Expresion_symbols[i])
				{
					++it;

					return -i;
				}
			throw INCORRECT_EXPRESSION;
		}
	}

public:

	void set_expression(char s[])
	{
		it = 0;

		expr[it++] = '0';
		if(s[0]!='\0' && s[0]!='-')
			expr[it++] = '+';

		for (int i=0; s[i] != '\0'; ++i)
		{
			expr[it++] = s[i];

			if (s[i] == '(')
			{
				expr[it++] = '0';
				if(s[i+1]!='\0' && s[i+1]!='-')
					expr[it++] = '+';
			}
		}

		expr[it]='\0';

		polish_expr.clear();
		stk.clear();

		for (it = 0; expr[it] != '\0';)
		{
			int nr = parse_number(expr);

			if (nr>=0)
				polish_expr.push_back(nr);
			else
			{
				if (Expresion_symbols[-nr] == ')')
				{
					while (stk.size() && Expresion_symbols[-stk.back()] != '(')
					{
						polish_expr.push_back(stk.back());
						stk.pop_back();
					}
					if (stk.size())
						stk.pop_back();
					else
						throw INCORRECT_EXPRESSION;
				}
				else if (Expresion_symbols[-nr] == '(')
					stk.push_back(nr);
				else
				{
					while (stk.size() && Priority_symbols[-stk.back()]>= Priority_symbols[-nr] && Expresion_symbols[-stk.back()]!='(')
					{
						polish_expr.push_back(stk.back());
						stk.pop_back();
					}
					stk.push_back(nr);
				}
			}

		}

		while (stk.size())
		{
			polish_expr.push_back(stk.back());
			stk.pop_back();
		}

	}

	int get_result()
	{
		int a = 0, b = 0;
		stk.clear();

		for (int i = 0; i < polish_expr.size(); ++i)
		{
			if (polish_expr[i] < 0)
			{
				if (stk.size())
				{
					b = stk.back();
					stk.pop_back();
				}
				else
					throw INCORRECT_EXPRESSION;

				if (stk.size())
				{
					a = stk.back();
					stk.pop_back();
				}
				else
					throw INCORRECT_EXPRESSION;

				if (Expresion_symbols[-polish_expr[i]] == '+')
				{
					stk.push_back(a + b);
				}
				else if (Expresion_symbols[-polish_expr[i]] == '-')
				{
					stk.push_back(a - b);
				}
				else if (Expresion_symbols[-polish_expr[i]] == '*')
				{
					stk.push_back(a*b);
				}
				else if (Expresion_symbols[-polish_expr[i]] == '/')
				{
					stk.push_back(a / b);
				}
				else
				{
					throw INCORRECT_EXPRESSION;
				}

			}
			else
			{
				stk.push_back(polish_expr[i]);
			}

		}
		if(stk.size()>1)
			throw INCORRECT_EXPRESSION;

		return stk.back();
	}

};

vector<int> stk;

int main()
{
	in >> expr;

	Expression_evaluator expression;

	try
	{
		expression.set_expression(expr);

		out << expression.get_result();
	}
	catch (int e)
	{
		out << "Incorrect expression";
	}

	return 0;
}