Cod sursa(job #2033438)

Utilizator robuvedVictor Robu robuved Data 6 octombrie 2017 20:02:00
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.46 kb
#include <fstream>
#include <stack>
#include <cstring>
using namespace std;

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

const int MAX = 1e5 + 1;
char s[MAX];
char *p = s;

bool isOperator(char c)
{
	return c == '+' || c == '-' || c == '*' || c == '/';
}
int Priority(char c)
{
	switch(c)
	{
		case '-':
		case '+': return 0;
		case '/':
		case '*': return 1;
		case '(': return -1;
	}
}
struct Element
{
	int value;
	bool isOperator;
};
Element fp[MAX];

char operators[2][3] = { "+-", "/*" };
const int maxLevel = 2;
int DoOperator(int first, int second, char c)
{
	switch (c)
	{
	case '+': return first + second;
	case '-': return first - second;
	case '*': return first * second;
	case '/': return first / second;
	}
}
struct Node
{
	int val;
	char oper;
	Node* left,* right;
	Node(int v = 0, char op = 0, Node* ll = nullptr, Node* rr = nullptr) : val(v), oper(op), left(ll), right(rr) {}
};

Node* BuildTree(int lev)
{
	
	if (lev == maxLevel)
	{
		if (*p == '(')
		{
			p++;
			Node * node = BuildTree(0);
			p++;
			return node;
		}
		else
		{
			int r = 0;
			while (*p >= '0' && *p <= '9')
			{
				r = r * 10 + *p - '0';
				p++;
			}
			Node * node = new Node(r, 0, nullptr, nullptr);
			return node;
		}
	}
	else
	{
		Node *node = BuildTree(lev + 1);
		while (*p && strchr(operators[lev], *p))
		{
			char op = *p++;
			Node *opNode = new Node(0, op, node, BuildTree(lev + 1));
			node = opNode;
		}
		return node;
	}
}

int EvalTree(Node* root)
{
	if (root->left == nullptr && root->right == nullptr)
	{
		return root->val;
	}
	else
	{
		return DoOperator(EvalTree(root->left), EvalTree(root->right), root->oper);
	}
}
int LevelEval(int lev)
{
	int r = 0;
	if (lev == maxLevel)
	{
		if (*p == '(')
		{
			p++;
			r = LevelEval(0);
			p++;
		}
		else
		{
			while (*p >= '0' && *p <= '9')
			{
				r = r * 10 + *p - '0';
				p++;
			}
		}
	}
	else
	{
		r = LevelEval(lev + 1);
		while (*p && strchr(operators[lev], *p))
		{
			char op = *p++;
			r = DoOperator(r, LevelEval(lev + 1), op);
		}
	}
	return r;
}
int Eval();

int Factor()
{
	int f = 0;
	if (*p == '(')
	{
		++p;
		f = Eval();
		p++;
	}
	else
	{
		while (*p >= '0' && *p <= '9')
		{
			f = f * 10 + *p - '0';
			p++;
		}
	}
	return f;
}
int Termen()
{
	int f = Factor();
	while (*p == '*' || *p == '/')
	{
		int c = *p; p++;
		if (c == '*')
		{
			f *= Factor();
		}
		else if (c == '/')
		{
			f /= Factor();
		}
	}
	return f;
}
int Eval()
{
	int t = Termen();
	while (*p == '+' || *p == '-')
	{
		int c = *p; p++;
		if (c == '+')
		{
			t += Termen();
		}
		else if (c == '-')
		{
			t -= Termen();
		}
	}
	return t;
}

int EvalStack(char *s, int len)
{
	stack<char> operatori;
	int k = 0;
	for (int i = 0; i < len; i++)
	{
		char c = s[i];
		if (c == '(')
		{
			operatori.push(s[i]);
		}
		else if (isOperator(c))
		{
			while (!operatori.empty() && Priority(c) <= Priority(operatori.top()))
			{
				Element el;
				el.value = operatori.top();
				el.isOperator = true;
				operatori.pop();
				fp[k++] = el;
			}
			operatori.push(c);
		}
		else if (c == ')')
		{
			while (operatori.top() != '(')
			{
				Element el;
				el.value = operatori.top();
				el.isOperator = true;
				operatori.pop();
				fp[k++] = el;
			}
			operatori.pop();
		}
		else
		{
			int number = c - '0';
			i++;
			while (i < len && s[i] >= '0' && s[i] <= '9')
			{
				number = number * 10 + (s[i] - '0');
				i++;
			}
			i--;
			Element el;
			el.value = number;
			el.isOperator = false;
			fp[k++] = el;
		}
	}
	while (!operatori.empty())
	{
		Element el;
		el.value = operatori.top();
		el.isOperator = true;
		operatori.pop();
		fp[k++] = el;
	}
	stack<int> operanzi;
	for (int i = 0; i < k; i++)
	{
		if (fp[i].isOperator)
		{
			int op1 = operanzi.top();
			operanzi.pop();
			int op2 = operanzi.top();
			operanzi.pop();
			double rez = 0;
			switch (fp[i].value)
			{
			case '-': rez = op2 - op1;
				break;
			case '+': rez = op1 + op2;
				break;
			case '*': rez = op1 * op2;
				break;
			case '/': rez = (double)op2 / op1;
				break;
			}
			operanzi.push(rez);
		}
		else
		{
			operanzi.push(fp[i].value);
		}
	}
	return operanzi.top();
}
int main()
{
	in >> s;
	int len = strlen(s);
	//out << EvalS	tack(s, len) << endl;
	//out << LevelEval(0) << endl;
	out << EvalTree(BuildTree(0));

}