Cod sursa(job #1420260)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 18 aprilie 2015 00:15:49
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.88 kb
#include <bits/stdc++.h>

std::ifstream fin("evaluare.in");
std::ofstream fout("evaluare.out");

class Token {
private:
	int value;
	bool isNr;
public:
	Token() {
		value = 0;
		isNr = 1;
	}
	Token(char t) {
		this->isNr = 0;
		if (t == '+') {
			this->value = 1;
		} else if (t == '-') {
			this->value = 0;
		} else if (t == '*') {
			this->value = 2;
		} else if (t == '/') {
			this->value = 3;
		} else if (t == '(') {
			this->value = -1;
		} else if (t == ')') {
			this->value = -2;
		}
	}
	Token(int nr) {
		this->isNr = 1;
		this->value = nr;
	}
	~Token() {}
	int getValue() {
		return this->value;
	}
	bool isOper() {
		return !isNr;
	}
	int opLevel() {
		if (value == 1) return 1;
		if (value == 0) return 1;
		if (value == 2) return 2;
		if (value == 3) return 2;
		if (value == -1) return 0;
		if (value == -2) return 0;
		return 0;
	}
	char getSign() {
		if (this->isOper()) {
			if (value == 1) return '+';
			if (value == 0) return '-';
			if (value == 2) return '*';
			if (value == 3) return '/';
			if (value == -1) return '(';
			if (value == -2) return ')';
		}
		return 0;
	}
};

std::vector<Token> tokens;

bool isNumeric(char c) {
	if (c >= '0' && c <= '9')return 1; else return 0;
}

void parseExp(std::string expr) {
	tokens.push_back(Token(0));
	tokens.push_back(Token('+'));
	for (unsigned int i = 0; i < expr.length(); ++i) {
		if (expr[i] == '(') {
			tokens.push_back(Token('('));
			tokens.push_back(Token(0));
			tokens.push_back(Token('+'));
		} else if (expr[i] == ')') {
			tokens.push_back(Token(')'));
		} else if (expr[i] == '*') {
			tokens.push_back(Token('*'));
		} else if (expr[i] == '/') {
			tokens.push_back(Token('/'));
		} else if (expr[i] == '+') {
			tokens.push_back(Token('+'));
		}  else if (expr[i] == '-') {
			tokens.push_back(Token('-'));
		} else if (isNumeric(expr[i])) {
			int nr = 0;
			while (isNumeric(expr[i])) {
				nr *= 10;
				nr += (int)expr[i] - (int)'0';
				++i;
			}
			--i;
			tokens.push_back(Token(nr));
		}
	}
	for (std::vector<Token>::iterator it = tokens.begin(); it != tokens.end() - 1; ++it) {
		if (it->isOper()) {
			if (it->getSign() == '+' && (it + 1)->getSign() == '-') {
				tokens.erase(it);
				--it;
			}
		}
	}
}

std::stack<Token> opStack, rsStack;
std::queue<Token> output;

int main() {
	std::string expresie;
	fin >> expresie;
	parseExp(expresie);
	for (std::vector<Token>::iterator it = tokens.begin(); it != tokens.end(); ++it) {
		if (!it->isOper()) {
			output.push(*it);
		} else {
			if (it->getSign() == '(') {
				opStack.push(*it);
			} else if (it->getSign() == ')') {
				while ((opStack.top()).getSign() != '(') {
					output.push(opStack.top());
					opStack.pop();
				}
				opStack.pop();
			} else {
				while (1) {
					if (opStack.empty()) break;
					if ((opStack.top().opLevel() < it->opLevel())) break;
					output.push(opStack.top());
					opStack.pop();
				}
				opStack.push(*it);
			}
		}
	}
	while (!opStack.empty()) {
		output.push(opStack.top());
		opStack.pop();
	}
	// for (std::vector<Token>::iterator it = tokens.begin(); it != tokens.end(); ++it) {
	// 	if (!it->isOper()) {
	// 		std::cout << it->getValue() << "\n";
	// 	} else {
	// 		std::cout << it->getSign() << "\n";
	// 	}
	// }
	// std::cout << "\n=====\n";
	while (!output.empty()) {
		Token tok = output.front();
		output.pop();
		// if (!tok.isOper()) {
		// 	std::cout << tok.getValue() << "\n";
		// } else {
		// 	std::cout << tok.getSign() << "\n";
		// }
		if (tok.isOper()) {
			int b = rsStack.top().getValue();
			rsStack.pop();
			int a = rsStack.top().getValue();
			rsStack.pop();
			//std::cout << a << " " << tok.getSign() << " " << b << "\n";
			if (tok.getSign() == '-') rsStack.push(Token(a - b));
			if (tok.getSign() == '/') rsStack.push(Token(a / b));
			if (tok.getSign() == '+') rsStack.push(Token(a + b));
			if (tok.getSign() == '*') rsStack.push(Token(a * b));
		} else {
			rsStack.push(tok);
		}
	}

	fout << rsStack.top().getValue() << "\n";
	return 0;
}