Cod sursa(job #2733194)

Utilizator Ghindea_DanielGhindea Daniel Ghindea_Daniel Data 30 martie 2021 08:58:45
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.02 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define lim 10005

using namespace std;
ifstream in("date.in");
ofstream out("date.out");

/// determin valoarea unei expresii aritmetice utilizand forma poloneza a acesteia

struct ceva{
    bool tip; int val;
}efp[lim];
char op[lim];
int prior[lim];

struct binar{
    int val; bool tip;
    binar *st, *dr;
}*rad;

int k = 0 , n; /// k - dimensiunea efp si p; n - dimensiunea op
void input()
{
    bool ok = false;
    int j = 0, numar = 0; ///j - coeficient prioritate; numar - var pt cal operanzilor
    for(int i = 0; i <= n; i++)
    {
        //if(op[i] >= '0' && op[i] <= '9') {efp[++k].val = op[i]; efp[k].tip = 0; prior[k] = 1000+j;}
        if(op[i] >= '0' && op[i] <= '9') {ok = true; numar = numar*10+(op[i] - '0');}
            else
            {
                if(ok == true)  {efp[++k].val = numar; efp[k].tip = 0; prior[k] = 1000+j; numar = 0; ok = false;}
                if(op[i] == '(') j += 10;
                if(op[i] == ')') j -= 10;
                if(op[i] == '+' || op[i] == '-') {efp[++k].val = op[i]; efp[k].tip = 1; prior[k] = 1+j;}
                if(op[i] == '*' || op[i] == '/') {efp[++k].val = op[i]; efp[k].tip = 1; prior[k] = 10+j;}
            }
    }
}

int mic(int st, int dr)
{
    int mn = 2000,poz;
    for(int i = dr; i >= st; i--)
        if(prior[i] < mn && prior[i] != 0) {mn = prior[i]; poz = i;}
    return poz;
}

void make(binar *&r, int st, int dr)
{
    int x = mic(st,dr);
    r->val = efp[x].val; r->tip = efp[x].tip;
    if(r->tip == 0) {r->st = r->dr =NULL;}
        else
        {
            prior[x] = 0;
            binar *q = new binar,*u = new binar;
            r->st = q;
            r->dr = u;
            make(q,st,x);
            make(u,x,dr);
        }
}

void SRD(binar *p)
{
    if(p != NULL)
    {
        SRD(p->dr);
        if(p->tip == 0) cout<<p->val<<' ';
            else cout<<char(p->val)<<' ';
        SRD(p->st);
    }
}
int expresie(binar *r, float &sum)
{
    if(r->st == NULL && r->dr == NULL)  return r->val;
        else
        {
            float a = expresie(r->st,sum);
            float b = expresie(r->dr,sum);
            if(r->val == '+')   sum = a+b;
            if(r->val == '-')   sum = a-b;
            if(r->val == '*')   sum = a*b;
            if(r->val == '/')   sum = a/b;
        }
    return sum;
}
int main()
{
    in.getline(op,lim); ///citesc sirul
    n = strlen(op);
    input();            ///adaug elementele specifice in efp si prior
    rad = new binar;
    make(rad,1,k);      ///creez arborele binar in forma poloneza
   // cout<<op<<'\n';
    float xp;
    if(rad->val == '+' || rad->val == '-') xp = 0;
        else xp = 1;
    out<<expresie(rad,xp);
    return 0;
}

    /*for(int i = 1; i <= k; i++)
        if(efp[i].tip == 0) cout<<efp[i].val<<' ';
            else    cout<<char(efp[i].val)<<' ';*/
    /*for(int i = 1; i <= k; i++)
        cout<<prior[i]<<' ';*/
    //SRD(rad);
    //cout<<'\n';