Cod sursa(job #2128007)

Utilizator Neamtu_StefanStefan Neamtu Neamtu_Stefan Data 11 februarie 2018 12:48:57
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.97 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+=1;
                break;
            case ')' :
                paranteze-=1;
                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 << " ";
    }
}

int interpretare(nod *c){
    switch(c->info)
    {
        case '+' :
            return interpretare(c->st) + interpretare(c->dr);
        case '-' :
            return interpretare(c->st) - interpretare(c->dr);
        case '*' :
            return interpretare(c->st) * interpretare(c->dr);
        case '/' :
            return interpretare(c->st) / interpretare(c->dr);
        default :
            return c->oper;
    }
}

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

    fout << interpretare(prim);

    return 0;