Cod sursa(job #2730794)

Utilizator Ghindea_DanielGhindea Daniel Ghindea_Daniel Data 26 martie 2021 21:13:29
Problema Evaluarea unei expresii Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define lim 10005
#include <vector>
using namespace std;
ifstream in("evaluare.in");
ofstream out("evaluare.out");

///TO DO learn what this " vector efp<pair int, int>; " means + pushback
struct ceva{
    bool tip; int val;
}efp[lim];
char op[lim];
int prior[lim];

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

int k = 0 , n; /// k - dimensiunea efp si p; n - dimensiunea op

void input()
{
    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] == '(') 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 = st; i <= dr; 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;
    if(r->val >= '0' && r->val <= '9') {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->st);
        cout<<char(p->val)<<' ';
        SRD(p->dr);
    }
}
int expresie(binar *r, float &sum)
{
    if(r->st == NULL && r->dr == NULL)  return (r->val - 48);
        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
    //SRD(rad);
    //cout<<'\n';

    float xp;
    if(rad->val == '+' || rad->val == '-') xp = 0;
        else xp = 1;
    cout<<expresie(rad,xp);
    return 0;
}