Cod sursa(job #3293166)

Utilizator DalvDalvGhita Vladut DalvDalv Data 10 aprilie 2025 15:03:56
Problema Evaluarea unei expresii Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <iostream>
#include <sstream>
#include <string>
#include <functional>
#include <fstream>
#include <queue>
#include <stack>
#include <unordered_map>
#include <cstring>

using namespace std;

const int modulo = 1000000000;

int op_add(int lhs, int rhs) {
	return lhs + rhs;
}

int op_sub(int lhs, int rhs) {
	return lhs - rhs;
}

int op_mul(int lhs, int rhs) {
	return lhs * rhs;
}

int op_div(int lhs, int rhs) {
	return lhs / rhs;
}

int main() {
	ifstream fin("evaluare.in");
	ofstream fout("evaluare.out");

	string expression;
	getline(fin, expression);

	queue<int> outputQueue;
	stack<pair<int, int>> operatorStack;

	function<int(int,int)> funcs[] = {
		op_add, op_sub, op_mul, op_div
	};
	int opPrecedence[] = {1, 1, 2, 2};
	unordered_map<char, int> opMap = {
		{'+', 0 + modulo},
		{'-', 1 + modulo},
		{'*', 2 + modulo},
		{'/', 3 + modulo}
	};

	for(int i = 0; i < expression.length(); i++) {
		if(!strchr("()+-*/", expression[i])) {
			int nr = 0;
			do {
				nr *= 10;
				nr += expression[i] - '0';
				i++;
			}while(!strchr("()+-*/", expression[i]));

			outputQueue.push(nr);

			i--;
			continue;
		}

		if(expression[i] == '(') {
			operatorStack.push(make_pair('(', 0));
			continue;
		}

		if(expression[i] == ')') {
			while(operatorStack.top().first != '(') {
				outputQueue.push(operatorStack.top().first);
				operatorStack.pop();
			}
			operatorStack.pop();
			continue;
		}

		int opIndex = opMap[expression[i]];
		int precedence = opPrecedence[opIndex - modulo];

		while(operatorStack.size() > 0 && operatorStack.top().second > precedence) {
			outputQueue.push(operatorStack.top().first);
			operatorStack.pop();
		}
		operatorStack.push(make_pair(opIndex, precedence));
	}

	while(operatorStack.size() > 0) {
		outputQueue.push(operatorStack.top().first);
		operatorStack.pop();
	}

	stack<int> evalStack;

	while(outputQueue.size() > 0) {
		if(outputQueue.front() >= modulo) {
			int opIndex = outputQueue.front() - modulo;
			int rhs = evalStack.top(); evalStack.pop();
			int lhs = evalStack.top(); evalStack.pop();

			evalStack.push(funcs[opIndex](lhs, rhs) % modulo);
		} else {
			evalStack.push(outputQueue.front());
		}

		outputQueue.pop();
	}

	int res = evalStack.top();
	fout << res << endl;

	return 0;
}