Cod sursa(job #867464)

Utilizator fhandreiAndrei Hareza fhandrei Data 29 ianuarie 2013 18:37:23
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
// Include
#include <fstream>
#include <cstring>
#include <utility>
using namespace std;

// Definitii
#define mp make_pair

#define opr pair<int, int>
#define id first
#define grade second

// Constante
const int sz = (int)1e5+1;
const int oo = (1<<30)-1;

// Functii
int RSD(int left, int right);

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

char expresion[sz];

int operatorsNum;
opr operators[sz];

// Main
int main()
{
    in >> expresion;
	int expLen = strlen(expresion);
	int bracketsLevel = 0;
	for(int i=0 ; i<expLen ; ++i)
	{
		switch(expresion[i])
        {
            case '(':
            {
                ++bracketsLevel;
                break;
            }
            case ')':
            {
                --bracketsLevel;
                break;
            }
            case '+':
            case '-':
            {
                int currentGrade = bracketsLevel*2;
                operators[++operatorsNum] = mp(i, currentGrade);
                break;
            }
            case '*':
            case '/':
            {
                int currentGrade = bracketsLevel*2 + 1;
                operators[++operatorsNum] = mp(i, currentGrade);
                break;
            }
        }
	}
	
	operators[++operatorsNum] = mp(oo, oo);
	
    out << RSD(0, expLen-1);
	
    in.close();
    out.close();
    return 0;
}


int RSD(int left, int right)
{
    int operatorGrade=oo, operatorPos;
	int start = lower_bound(operators+1, operators+operatorsNum, mp(left,0)) - operators;
	
	for(int i=start ; operators[i].id<=right ; ++i)
	{
		if(operators[i].grade < operatorGrade)
		{
			operatorGrade = operators[i].grade;
			operatorPos = operators[i].id;
		}
	}
	
    if(operatorGrade != oo)
    {
        left = RSD(left, operatorPos-1);
        right = RSD(operatorPos+1, right);
		
        switch(expresion[operatorPos])
        {
            case '+': return left+right;
            case '-': return left-right;
            case '*': return left*right;
            case '/': return left/right;
        }
    }
	
    int num = 0;
    for(int i=left ; i<=right ; ++i)
        if(expresion[i] != '(' && expresion[i] !=')')
            num = num*10 + (expresion[i]-48);
	
    return num;
}