Cod sursa(job #2259016)

Utilizator Steff94Stefan Steff94 Data 12 octombrie 2018 20:33:47
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 4.08 kb
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<stack> 
#include<cstdlib>
#include<cctype>
using namespace std;

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

int precedence(string str) {
	if (!str.empty()){
	if (str.compare("+") == 0)
		return 2;
	if (str.compare("-") == 0)
		return 2;
	if (str.compare("*") == 0)
		return 3;
	if (str.compare("/") == 0)
		return 3;
	}
	return 0;
}

int asociativity(string str) {
	if (!str.empty()) {
		if (str.compare("+") == 0)
			return 1;
		if (str.compare("-") == 0)
			return 1;
		if (str.compare("*") == 0)
			return 1;
		if (str.compare("/") == 0)
			return 1;
	}
	return 0;
}
bool is_number(const std::string& s)
{
	std::string::const_iterator it = s.begin();
	while (it != s.end() && std::isdigit(*it)) ++it;
	return !s.empty() && it == s.end();
}


int main()
{
	std::string s;
	std::string build;
	std::string::iterator it;
	in >> s;
	//out << s;
	queue <string> init_queue;
	int ok = 0;
	it = s.begin();
	while(it != s.end()){
		if (*it == ')' || *it == '+' || *it == '(' || *it == '-' || *it == '*' || *it == '/') {
			if (ok == 1) {
				init_queue.push(build);
				build.clear();
				ok = 0;
			}
			std::string convert_char_to_string(1, *it);
			init_queue.push(convert_char_to_string);
		}

		if (*it == '0' || *it == '1' || *it == '2' || *it == '3' || *it == '4' || *it == '5' || *it == '6' || *it == '7' || *it == '8' || *it == '9') {
			build.push_back(*it);
			ok = 1;
		}
		it++;
	}
	if (ok == 1) {
		init_queue.push(build);
		build.clear();
		ok = 0;
	}


	queue <string> shunting_yard_queue;
	stack <string> shunting_yard_stack;


	while (!init_queue.empty()) {
		string top = init_queue.front();
		if (is_number(top) == true)  {
			shunting_yard_queue.push(top);
		}
		// if (top == function)
		//     push to operator stack
		if (top == "+" || top == "-" || top == "*" || top == "/") {
			if (!shunting_yard_stack.empty()) {
				while (/*there is a function at top of operator stack || */ (precedence(shunting_yard_stack.top()) > precedence(top))
					|| ((precedence(shunting_yard_stack.top()) == precedence(top)) && (asociativity(shunting_yard_stack.top()) == 1))
					&& (shunting_yard_stack.top() != "(")
					) {
					shunting_yard_queue.push(shunting_yard_stack.top());
					shunting_yard_stack.pop();
					if (shunting_yard_stack.empty()) break;
					
				}
			}
			shunting_yard_stack.push(top);
		}
		if (top == "(") {
			shunting_yard_stack.push(top);
		}
		if (top == ")") {
			while (shunting_yard_stack.top() != "(") {
				shunting_yard_queue.push(shunting_yard_stack.top());
				shunting_yard_stack.pop();
			}
			if (shunting_yard_stack.top() == "(") {
				shunting_yard_stack.pop();
			}
		}
		init_queue.pop();
	}
	if (init_queue.empty()) {
		while (!shunting_yard_stack.empty()) {
			shunting_yard_queue.push(shunting_yard_stack.top());
			shunting_yard_stack.pop();
		}
	}

	/*
	cout << endl;
	cout << endl;
	cout << "----------------";
	cout << endl;

	while (!shunting_yard_queue.empty()) {
		cout << shunting_yard_queue.front() << " ";
		shunting_yard_queue.pop();
	}
	*/
	
	
	stack <string> final_stack;
	while (!shunting_yard_queue.empty()) {
		string top = shunting_yard_queue.front();
		if (top != "+" && top != "-" && top != "*" && top != "/") {
			final_stack.push(top);
		}
		else { //will be rerwite in a gud function : )
			string sign = shunting_yard_queue.front();
			string val1 = final_stack.top();
			final_stack.pop();
			string val2 = final_stack.top();
			final_stack.pop();
			string val3;
			if (sign == "+") {
				val3 = to_string(std::stoi(val2) + std::stoi(val1));
			}
			if (sign == "-") {
				val3 = to_string(std::stoi(val2) - std::stoi(val1));
			}
			if (sign == "*") {
				val3 = to_string(std::stoi(val2) * std::stoi(val1));
			}
			if (sign == "/") {
				val3 = to_string(std::stoi(val2) / std::stoi(val1));
			}
			final_stack.push(val3);
		}
		shunting_yard_queue.pop();
	}

	out << final_stack.top();
	

	//system("Pause");
	return 0;
}