Cod sursa(job #979078)

Utilizator BogdacutuSeniuc Bogdan Bogdacutu Data 31 iulie 2013 15:18:39
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evalueare.out");
string expr;
map<string, int> operators;
stack<string> polish;

void readExpression() {
	fin>>expr;
}

void prepareOperators() {
	operators["+"] = 0;
	operators["-"] = 0;
	operators["/"] = 5;
	operators["*"] = 5;
}

bool isOperator(char op) {
	return (operators.find(string(1, op)) != operators.end());
}

bool isOperator(string op) {
	return (operators.find(op) != operators.end());
}

int comparePrecedence(char op1, string op2) {
	return operators[string(1, op1)] - operators[op2];
}

void toPolish() {
	stack<string> out, aux;
	bool lastNum = false;
	char current;
	for (unsigned int i = 0; i < expr.length(); ++i) {
		current = expr.at(i);
		if (current >= '0' && current <= '9') {
			if (lastNum) {
				string num = out.top();
				out.pop();
				out.push(num+current);
			} else {
				out.push(string(1, current));
				lastNum = true;
			}
		} else {
			if (isOperator(current)) {
				while (!aux.empty() && isOperator(aux.top())) {
					if (comparePrecedence(current, aux.top()) <= 0) {
						out.push(aux.top());
						aux.pop();
						continue;
					}
					break;
				}
				aux.push(string(1, current));
			} else if (current == '(') {
				aux.push(string(1, current));
			} else if (current == ')') {
				while (!aux.empty() && aux.top() != "(") {
					out.push(aux.top());
					aux.pop();
				}
				aux.pop();
			}
			lastNum = false;
		}
	}
	while (!aux.empty()) {
		out.push(aux.top());
		aux.pop();
	}
	while (!out.empty()) {
		polish.push(out.top());
		out.pop();
	}
}

void evaluate() {
	stack<unsigned long int> stack;
	char op;
	string token;
	unsigned long int result, a, b;
	while (!polish.empty()) {
		token = polish.top();
		if (isOperator(token)) {
			op = token.at(0);
			b = stack.top();
			stack.pop();
			a = stack.top();
			stack.pop();
			switch (op) {
				case '+':
					result = a + b;
					break;
				case '-':
					result = a - b;
					break;
				case '*':
					result = a * b;
					break;
				case '/':
					result = a / b;
					break;
			}
			stack.push(result);
		} else {
			stack.push(atoi(token.c_str()));
		}
		polish.pop();
	}
	fout<<stack.top()<<"\n";
}

int main() {
	readExpression();
	prepareOperators();
	toPolish();
	evaluate();
	return 0;
}