Cod sursa(job #867514)

Utilizator fhandreiAndrei Hareza fhandrei Data 29 ianuarie 2013 19:41:40
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.62 kb
// Include
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

// Definitii
#define leftSon (node<<1)
#define rightSon (node<<1)+1

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

// Functii
int RSD(int left, int right);
void update(int node, int left, int right);
void query(int node, int left, int right);

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

char expresion[sz];

int operatorsNum;
int operatorsID[sz];

int leftRange, rightRange;
int pos;
struct opr
{
	int grade;
	int id;
	bool operator< (opr a)
	{
		if(grade == a.grade)
			return id > a.id;
		return grade < a.grade;
	}
}	tree[treesz], val;

// Main
int main()
{
    in >> expresion;
	for(int i=1 ; i<=treesz ; ++i)
		tree[i].grade = oo;
	int expLen = strlen(expresion);
	int bracketsLevel = 0;
	for(int i=0 ; i<expLen ; ++i)
		if(expresion[i] == '+' || expresion[i] == '-' || expresion[i] == '*' || expresion[i] == '/')
			++operatorsNum;
	
	int currentOPs = 0;
	for(int i=0 ; i<expLen ; ++i)
	{
		switch(expresion[i])
        {
            case '(':
            {
                ++bracketsLevel;
                break;
            }
            case ')':
            {
                --bracketsLevel;
                break;
            }
            case '+':
            case '-':
            {
                int currentGrade = bracketsLevel*2;
                operatorsID[++currentOPs] = i;
				pos = currentOPs;
				val.grade = currentGrade;
				val.id = pos;
				update(1, 1, operatorsNum);
                break;
            }
            case '*':
            case '/':
            {
                int currentGrade = bracketsLevel*2 + 1;
                operatorsID[++currentOPs] = i;
				pos = currentOPs;
				val.grade = currentGrade;
				val.id = pos;
				update(1, 1, operatorsNum);
                break;
            }
        }
	}
	
	operatorsID[operatorsNum+1] = oo;
	
    out << RSD(0, expLen-1);
	
    in.close();
    out.close();
    return 0;
}


int RSD(int left, int right)
{
    int operatorGrade=oo, operatorPos;
	leftRange = lower_bound(operatorsID+1, operatorsID+operatorsNum+1, left) - operatorsID;
	rightRange = upper_bound(operatorsID+1, operatorsID+operatorsNum+1, right) - operatorsID - 1;
	if(leftRange <= rightRange)
	{
		val.grade = oo;
		val.id = 0;
		query(1, 1, operatorsNum);
		operatorGrade = val.grade;
		operatorPos = operatorsID[val.id];
        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;
}

void update(int node, int left, int right)
{
	if(left == right)
	{
		tree[node] = val;
		return;
	}
	int mid = (left + right) >> 1;
	
	if(pos <= mid)
		update(leftSon, left, mid);
	else
		update(rightSon, mid+1, right);
	
	tree[node] = (tree[leftSon] < tree[rightSon])? tree[leftSon] : tree[rightSon];
}

void query(int node, int left, int right)
{
	if(leftRange <= left && right <= rightRange)
	{
		if(tree[node] < val)
			val = tree[node];
		return;
	}
	
	int mid = (left + right) >> 1;
	if(leftRange <= mid)
		query(leftSon, left, mid);
	if(mid < rightRange)
		query(rightSon, mid+1, right);
}