Cod sursa(job #2016464)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 29 august 2017 14:33:59
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
#include <cstdio>

using namespace std;

FILE *in,*out;

const int nmax = 100000;

char c[nmax+3];

struct Symbol
{
    int tip;
    char semn;
    int val;
    int prior;
} v[1+nmax];

int n;

int jump[1+nmax][3];
int last[1+nmax][3];

int prioritate(char x)
{
    if(x == '-' || x == '+')
        return 1;
    return 2;
}

void parsare()
{
    int i = 0;
    while(c[i] != '\0')
    {
        if(c[i] == '-' || c[i] == '+' || c[i] == '*' || c[i] == '/')
        {
            v[++n].tip = 3;
            v[n].semn = c[i];
            v[n].prior = prioritate(c[i]);
        }
        else if(c[i] == '(')
            v[++n].tip = 1;
        else if(c[i] == ')')
            v[++n].tip = 2;
        else if(c[i] >= '0' && c[i] <= '9')
        {
            int nr = 0;
            while(c[i] >= '0' && c[i] <= '9')
            {
                nr *= 10;
                nr += (c[i] - '0');
                i ++;
            }
            v[++n].tip = 4;
            v[n].val = nr;
            i --;
        }
        i ++;

    }
}

void precalculare()
{
    int level = 0;
    jump[1][2] = 0;
    jump[1][1] = 0;
    for(int j = 1; j <= 2; j ++)
    {
        for(int i = 2; i <= n; i ++)
        {
            if(v[i-1].tip == 1)
                level ++;
            if(v[i].tip == 2)
            {
                level --;
                jump[i][j] = last[level][j];
            }
            if(v[i].tip == 3)
            {
                jump[i][j] = last[level][j];
                if(v[i].prior == j)
                    last[level][j] = i;
            }
            if(v[i].tip == 4)
                jump[i][j] = last[level][j];
        }
    }

}

int root;

int left[1+nmax],right[1+nmax];

int buildtree(int from,int to)
{
    if(from == to)
    {
        return to;
    }
    else
    {
        int node = jump[to][1];
        if(node == 0 || node < from)
            node = jump[to][2];
        if(node == 0 || node < from)
            return buildtree(from+1,to-1);
        else
            {
                left[node] = buildtree(from,node-1);
                right[node] = buildtree(node+1,to);
                return node;
            }
    }
}

int calculare(int node)
{
    if(v[node].tip == 3)
    {
        if(v[node].semn == '+')
            return calculare(left[node]) + calculare(right[node]);
        if(v[node].semn == '-')
            return calculare(left[node]) - calculare(right[node]);
        if(v[node].semn == '*')
            return calculare(left[node]) * calculare(right[node]);
        if(v[node].semn == '/')
            return calculare(left[node]) / calculare(right[node]);
    }
    if(v[node].tip == 4)
    {
        return v[node].val;
    }
}

int main()
{
    in = fopen("evaluare.in","r");
    out = fopen("evaluare.out","w");
    fgets(c,nmax+3,in);
    parsare();
    precalculare();
    root = buildtree(1,n);
    fprintf(out,"%d",calculare(root));
    return 0;
}