Cod sursa(job #1010747)

Utilizator nimeniaPaul Grigoras nimenia Data 15 octombrie 2013 17:24:55
Problema Evaluarea unei expresii Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <utility>
#include <string>
#include <vector>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef map<string, int> msi;
typedef long long ll;
typedef unsigned long long ull;

typedef vector<int>::iterator vit;
typedef vector<ii>::iterator viit;
typedef vector<string>::iterator vst;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORD(i, a, b) for (int i = a-1; i >= b; --i)
#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(), x.end()
#define SIZE(x) (int)(x).size()
#define FOREACH(it, c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); ++it)
#define INF 1023456789
#define DEBUG(x) //cerr << #x << ": " << x << endl;
#define ERR(...) fprintf(stderr, __VA_ARGS__);

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

string ops("+-*/");

int precs[] = { 10, 15, 20, 35 };
int assocs[] = { 1, 0, 1, 0 };

string to_string(char c) {
	string op;
	stringstream ss;
	ss << c;
	ss >> op;
	return op;
}

int prec(char op) {
	int pos = ops.find(op);
	if (pos == string::npos)
		return -1;
	return precs[pos];
}

int main() {

	string expr;
	f >> expr;

	queue < string > output;
	stack<char> operators;

	bool have_num = false;
	string num = "";

	FOR(i, 0, expr.size()) {
		char c = expr[i];
		DEBUG(c);
		if (isdigit(c)) {
			have_num = true;
			num += c;
		} else {
			if (have_num) {
				output.push(num);
				num = "";
				have_num = false;
			}

			if (c == '(') {
				operators.push(c);
				continue;
			}

			if (c == ')') {
				DEBUG("Bracket")
				while (!operators.empty() && operators.top() != '(') {
					output.push(to_string(operators.top()));
					operators.pop();
				}
				if (!operators.empty() && operators.top() == '(')
					operators.pop();
				continue;
			}

			if (ops.find(c) != string::npos) {
				if (have_num) {
					output.push(num);
					num = "";
					have_num = false;
				}

				DEBUG("0HERE");

				int p = prec(c);
				DEBUG("1HERE");

				while (!operators.empty() && prec(operators.top()) >= p) {
					output.push(to_string(operators.top()));
					operators.pop();
				}
				operators.push(c);

			}
		}
	}

	if (have_num) {
		output.push(num);
	}
	while (!operators.empty()) {
		output.push(to_string(operators.top()));
		operators.pop();
	}

	stack<int> rez_stack;

	while (!output.empty()) {
		string tos = output.front();
		DEBUG(tos);
		output.pop();
		int rez;
		if (ops.find(tos) != string::npos) {
			int op1 = rez_stack.top();
			rez_stack.pop();
			int op2 = rez_stack.top();
			rez_stack.pop();
			if (tos == "+")
				rez = op2 + op1;
			else if (tos == "-")
				rez = op2 - op1;
			else if (tos == "/")
				rez = op2 / op1;
			else if (tos == "*")
				rez = op2 * op1;
		} else {
			rez = atoi(tos.c_str());
		}
		rez_stack.push(rez);
		DEBUG(rez_stack.top());
	}

	g << rez_stack.top() << endl;

	return 0;
}