Cod sursa(job #2122044)

Utilizator Neamtu_StefanStefan Neamtu Neamtu_Stefan Data 4 februarie 2018 16:21:16
Problema Evaluarea unei expresii Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.39 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

struct nod{
    char info;
    int oper;
    nod *st, *dr;
};

string expresie;
vector < pair <int, char> > prioritati;
vector <int> operanzi;

void initializare()
{
    fin >> expresie;
    int paranteze=0, cnt_numere=0;
    for(int i=0; expresie[i]!='\0'; ++i)
        switch(expresie[i])
        {
            case '(' :
                paranteze+=10;
                break;
            case ')' :
                paranteze-=10;
                break;
            case '+' :
                prioritati.push_back(make_pair (1+paranteze, '+'));
                break;
            case '-' :
                prioritati.push_back(make_pair (1+paranteze, '-'));
                break;
            case '/' :
                prioritati.push_back(make_pair (10+paranteze, '/'));
                break;
            case '*' :
                prioritati.push_back(make_pair (10+paranteze, '*'));
                break;
            default :
                prioritati.push_back(make_pair (1000+paranteze, cnt_numere+++'0'));
                int nr=expresie[i]-'0';
                if (strchr("+-*/()", expresie[i+1]))
                {
                    operanzi.push_back(nr);
                    break;
                }
                while(++i && strchr("1234567890", expresie[i+1]) && expresie[i+1]!='\0')
                    nr=nr*10+(expresie[i]-'0');
                nr=nr*10+(expresie[i]-'0');
                operanzi.push_back(nr);
                break;
        }
}

int minim(int st, int dr)
{
    if (dr-st==1)
        return st;
    int minim=9999999, poz=-1;
    for(int i=st; i<dr; ++i)
        if (prioritati[i].first < minim)
        {
            minim=prioritati[i].first;
            poz=i;
        }
    return poz;
}

nod *arborificare(int st, int dr)
{
    int poz=minim(st, dr);
    nod * p = new nod;
    if (strchr("+-*/", prioritati[poz].second))
    {
        p->info=prioritati[poz].second;
        p->st=arborificare(st, poz-1);
        p->dr=arborificare(poz+1, dr);
    }
    else
    {
        p->oper=operanzi[prioritati[st].second-'0'];
        p->st=NULL;
        p->dr=NULL;
    }
    return p;
}

void sdr(nod *c)
{
    if (c)
    {
        sdr(c->st);
        sdr(c->dr);
        if (strchr("+-*/",c->info))
            fout << c->info << " ";
        else
            fout << c->oper << " ";
    }
}

void interpretare(nod *c)
{
    if (c)
    {
        interpretare(c->st);
        interpretare(c->dr);
        switch(c->info)
        {
            case '+' :
                c->oper=c->st->oper + c->dr->oper;
                c->info='\0';
                break;
            case '-' :
                c->oper=c->st->oper - c->dr->oper;
                c->info='\0';
                break;
            case '*' :
                c->oper=c->st->oper * c->dr->oper;
                c->info='\0';
                break;
            case '/' :
                c->oper=c->st->oper / c->dr->oper;
                c->info='\0';
                break;
            default : return;
        }
    }
}

int main()
{
    initializare();
    nod *prim = arborificare(0, prioritati.size());

    interpretare(prim);

    fout << prim -> oper;

    return 0;
}