Cod sursa(job #3203484)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 13 februarie 2024 19:03:19
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 666013;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

map<string, int> priority{
	{ "*", 2 },
	{ "/", 2 },
	{ "%", 2 },
	{ "+", 1 },
	{ "-", 1 },
};

string expression;

vector<string> tokenize(const string& expression) {
	string token;
	vector<string> tokens;
	set<char> separators{
		'(', ')', '+', '-', '*', '/', '%'
	};
	for (auto& c : expression) {
		if (separators.count(c)) {
			if (token.size()) {
				tokens.push_back(token);
				token = "";
			}
			tokens.push_back(string(1, c));
		}
		else {
			token += c;
		}
	}
	return tokens;
}

bool is_number(const string& str) {
	return all_of(all(str), [&](char c) { return isdigit(c); });
}

ll calculate(ll a, ll b, string operation) {
	if (operation == "+") {
		return a + b;
	}
	if (operation == "-") {
		return a - b;
	}
	if (operation == "*") {
		return a * b;
	}
	if (operation == "/") {
		return a / b;
	}
	if (operation == "%") {
		return a / b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fin >> expression;
	expression = "(" + expression + ")";
	auto tokens = tokenize(expression);
	stack<string> operators;
	queue<string> output;
	for (auto& token : tokens) {
		if (is_number(token)) {
			output.push(token);
		}
		else if (token == "(") {
			operators.push(token);
		}
		else if (token == ")") {
			while (operators.top() != "(") {
				output.push(operators.top());
				operators.pop();
			}
			operators.pop();
		}
		else { // operator
			while (operators.size() && operators.top() != "(" && priority[operators.top()] >= priority[token]) {
				output.push(operators.top());
				operators.pop();
			}
			operators.push(token);
		}
	}
	while (operators.size()) {
		output.push(operators.top());
		operators.pop();
	}
	vector<ll> numbers;
	while (output.size()) {
		auto token = output.front();
		output.pop();
		if (is_number(token)) {
			numbers.push_back(stoi(token));
			continue;
		}
		numbers.end()[-2] = calculate(numbers.end()[-2], numbers.back(), token);
		numbers.pop_back();
	}
	fout << numbers.back();
}