Cod sursa(job #2656265)

Utilizator Alex_dudeDudescu Alexandru Alex_dude Data 7 octombrie 2020 12:28:01
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.28 kb
#define _CRT_SECURE_NO_WARNINGS
#define K_N_MAX 100001

#include<cstdio>

#include <queue>
#include <stack>

enum TermFlag {
	IsNumber = 0x1,
	IsOperator = 0x2,
	IsLeftParan = 0x4,
	IsRightParan = 0x8,
};

struct term {
	short flags;
	char* op;
	int* nr;
};

#define K

char expression[K_N_MAX];

std::queue<term> q = std::queue<term>();
std::stack<term> s = std::stack<term>();

FILE* in = fopen("evaluare.in", "r");
FILE* out = fopen("evaluare.out", "w");

short comparePrecedence(char o1, char o2)
{
	short r1 = (strchr("+-", o1) != NULL) ? 1 : 2;
	short r2 = (strchr("+-", o2) != NULL) ? 1 : 2;

	return r1 - r2;
}

int execute(char op, int a, int b)
{
	int res = 0;

	switch (op)
	{
	case '+': { res = a + b; break; }
	case '-': { res = a - b; break; }
	case '*': { res = a * b; break; }
	case '/': { res = a / b; break; }
	};

	return res;
}

void RPN()
{
	char* p = expression;

	// While there are tokens
	while (*p != '\0')
	{
		if (*p >= '0' && *p <= '9')
		{
			int nr = 0;

			while (*p >= '0' && *p <= '9')
			{
				nr = nr * 10 + (*p - '0');
				p++;
			}
			
			q.push({ IsNumber, NULL, new int(nr) });
		}
		else if (*p == '(')
		{
			s.push({ IsLeftParan, NULL, NULL });
			p++;
		}
		else if (*p == ')')
		{
			while (!(s.top().flags & IsLeftParan))
			{
				q.push(s.top());
				s.pop();
			}

			s.pop();
			p++;
		}
		else if (strchr("+-*/", *p) != NULL)
		{
			while (!s.empty() && (s.top().flags & IsOperator) && (comparePrecedence(*(s.top().op), *p) > 0 || (comparePrecedence(*(s.top().op), *p) == 0 && strchr("+*", *p) != NULL)) && !(s.top().flags & IsLeftParan))
			{
				q.push(s.top());
				s.pop();
			}

			s.push({ IsOperator, p, NULL });
			p++;
		}
	}

	while (!s.empty())
	{
		q.push(s.top());
		s.pop();
	}
}

void eval()
{
	while (!q.empty())
	{
		if (q.front().flags & IsOperator)
		{
			int x = *(s.top().nr); s.pop();
			int y = *(s.top().nr); s.pop();

			int res = execute(q.front().op[0], y, x); q.pop();

			s.push({ IsNumber, NULL, new int(res) });
		}
		else {
			s.push(q.front());
			q.pop();
		}
	}
}

int main()
{
	fgets(expression, K_N_MAX + 1, in);
	
	RPN();
	eval();

	fprintf(out, "%d", *(s.top().nr));

	fclose(in);
	fclose(out);

	return 0;
}