Cod sursa(job #630933)

Utilizator JBaccountCatalin JBaccount Data 6 noiembrie 2011 19:17:43
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>

#define MKP make_pair
#define PB push_back

using namespace std;

char expr[100005];

int answer(char op, int a, int b)
{
	if (op == '+') return a + b;
	if (op == '-') return a - b;
	if (op == '*') return a * b;
	if (op == '/') return a / b;
}

int basecase(int start, int stop)	
{
	for (int i = start; i <= stop; ++i) if (!isdigit(expr[i])) return 0;
	return 1;
}

pair< vector<int>,vector<int> > operators(int start, int stop)
{
	int lev = 0;
	vector <int> pm, md;
	for (int i = start; i <= stop; ++i)
		if (expr[i] == '(') ++lev;
		else if (expr[i] == ')') --lev;
		else if (lev == 0) 
				if (expr[i] == '+' || expr[i] == '-') pm.PB(i);
				else if (expr[i] == '*' || expr[i] == '/') md.PB(i);
	return MKP(pm, md);		
}

int number(int start, int stop)
{
	int ans = 0;
	for (int i = start; i <= stop; ++i) ans = ans * 10 + expr[i]-'0';
	return ans;
}

int evaluate(int start, int stop)
{
	if (basecase(start, stop)) return number(start, stop);
	pair< vector<int>,vector<int> > op = operators(start, stop);
	if (op.first.size() == 0 && op.second.size() == 0) return evaluate(start + 1, stop - 1);
	
	op.first.PB(stop+1);
	op.second.PB(stop+1);
	
	int res;
	
	if (op.first.size() > 1) 
	{
		res = evaluate(start, op.first[0] - 1);	
		for (int i = 0; i < op.first.size() - 1; ++i) res = answer(expr[op.first[i]], res, evaluate(op.first[i] + 1, op.first[i+1] - 1));
	}		
	else 	
	{
		res = evaluate(start, op.second[0] - 1);	
		for (int i = 0; i < op.second.size() - 1; ++i) res = answer(expr[op.second[i]], res, evaluate(op.second[i] + 1, op.second[i+1] - 1));
	}	
	
	return res;
}

int main()
{
	freopen ("evaluare.in", "r", stdin);
	freopen ("evaluare.out", "w", stdout);
	
	scanf ("%s", expr);
	
	//printf ("%d", evaluate(0,4));
	
	printf ("%d", evaluate(0, strlen(expr)-1));
	
	return 0;
}