Cod sursa(job #2872860)

Utilizator radu.z5Zamfirescu Radu Ioan radu.z5 Data 18 martie 2022 01:06:56
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int priority(char op)
{
	if (op == '+' || op == '-')
		return 1;
	if (op == '*' || op == '/')
		return 2;
	return 0;
}

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

int apply(char op, int op1, int op2)
{
	switch (op) {
		case '+':
			return op1 + op2;
		case '-':
			return op1 - op2;
		case '*':
			return op1 * op2;
		case '/':
			return op1 / op2;
		default:
			cout << "Operator to apply not found." << endl;
			return 0;
	}
}

int solve(string &exp)
{
	vector<char> operators_stack;
	vector<int> operands;

	for (int i = 0; i < (int) exp.size(); i++) {
		char c = exp[i];

		if ('0' <= c && c <= '9') {
			int num = 0;
			while ('0' <= exp[i] && exp[i] <= '9') {
				num = num * 10 + exp[i] - '0';
				i++;
			}
			operands.push_back(num);
			c = exp[i];
		}

		if (c == '(') {
			operators_stack.push_back(c);
			continue;
		}
		if (c == ')') {
			// aplic toti operatorii de dupa ultima paranteza deschisa ramasi
			// pe stiva si las rezultatul obtinut pe stiva de operanzi
			while (!operators_stack.empty()) {
				auto op = operators_stack.back();
				operators_stack.pop_back();
				if (op == '(') {
					break;
				} else {
					auto operand2 = operands.back();
					operands.pop_back();
					auto operand1 = operands.back();
					operands.pop_back();
					operands.push_back(apply(op, operand1, operand2));
				}
			}
			continue;
		}

		if (is_operator(c)) {
			if (operators_stack.empty()) {
				operators_stack.push_back(c);
			} else {
				// verific daca trebuie sa astept al doilea operand pentru
				// operatorul curent sau trebuie aplicat cel de dinainte
				// (din vf. stivei) pe ultimi 2 operanzi inainte de a fi
				// aplicat cel citit acum, i.e c
				while (priority(operators_stack.back()) >= priority(c)) {
					auto op = operators_stack.back();
					operators_stack.pop_back();

					auto operand2 = operands.back();
					operands.pop_back();
					auto operand1 = operands.back();
					operands.pop_back();

					operands.push_back(apply(op, operand1, operand2));

					if (operators_stack.empty())
						break;
				}
				operators_stack.push_back(c);
			}
		}
	}

	while (!operators_stack.empty()) {
		auto op = operators_stack.back();
		operators_stack.pop_back();

		auto operand2 = operands.back();
		operands.pop_back();
		auto operand1 = operands.back();
		operands.pop_back();
		operands.push_back(apply(op, operand1, operand2));
	}

	return operands.back();
}

int main()
{
	ifstream in("evaluare.in");
	ofstream out("evaluare.out");
	string exp;
	in >> exp;
	out << solve(exp);
	in.close();
	out.close();
	return 0;
}