Cod sursa(job #2663740)

Utilizator XeinIonel-Alexandru Culea Xein Data 27 octombrie 2020 10:17:11
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.95 kb
// Metoda ce se bazeaza pe arborele expresiei
// Transformare din infix in arbore

#include <fstream>

#define LMAX 100001

using namespace std;

struct arbore
{
    char tip; // V - numar, O - operator
    int val;
    char op;
    arbore *st, *dr;
};

arbore* St_Nod[LMAX];
char St_Op[LMAX];
int idx_expr = 0, idx_op = -1, idx_nod = -1;

// Daca operatia 'a' este '*' sau '/' atunci nu se poate realiza operatia imediat anterioara 'b' daca 'b' este '+' sau '-'
// (Al doilea operand al lui 'b' este primul operand al lui 'a' -> intai trebuie realizata operatia 'a')
int prioritate(char a, char b)
{
    if(a == '*' || a == '/')
        if(b == '+' || b == '-')
            return 0;
    return 1;
}

// Se realizeaza un arbore din doi subarbori luati din stiva St_Nod ce se leaga prin operatia din varful stivei St_Op
// Arborele rezultat este considerat un alt subarbore si se adauga in stiva St_Nod
void realizare_operatie()
{
    arbore* nod = new arbore;
    nod->tip = 'O';
    nod->op = St_Op[idx_op--];
    nod->dr = St_Nod[idx_nod--];
    nod->st = St_Nod[idx_nod--];

    St_Nod[++idx_nod] = nod;
}

arbore* Formare(char* expr)
{
    while(expr[idx_expr] != '\0')
    {
        if(expr[idx_expr] == '(')
        {
            St_Op[++idx_op] = '(';
            idx_expr++;
        }
        if(expr[idx_expr] == ')')
        {
            while(St_Op[idx_op] != '(')
                realizare_operatie();
            idx_op--;
            idx_expr++;
        }
        else if(expr[idx_expr] < '0')
        {
            while( idx_op > -1 && St_Op[idx_op] != '(' && prioritate(expr[idx_expr], St_Op[idx_op]))
                realizare_operatie();
            St_Op[++idx_op] = expr[idx_expr];
            idx_expr++;
        }
        else
        {
            int NR = 0;
            while(expr[idx_expr] >= '0' && expr[idx_expr] <= '9')
            {
                NR = NR * 10 + (expr[idx_expr] - '0');
                idx_expr++;
            }
            arbore* nod = new arbore;
            nod->tip = 'V';
            nod->val = NR;
            nod->st = NULL;
            nod->dr = NULL;
            St_Nod[++idx_nod] = nod;
        }
    }

    while(idx_op > -1)
        realizare_operatie();

    return St_Nod[0];
}

int Eval(arbore* nod)
{
    if(nod->tip == 'V')
        return nod->val;
    else
    {
        int STANGA = Eval(nod->st);
        int DREAPTA = Eval(nod->dr);
        switch (nod->op)
        {
        case '+':
            return STANGA + DREAPTA;
        case '-':
            return STANGA - DREAPTA;
        case '*':
            return STANGA * DREAPTA;
        case '/':
            return STANGA / DREAPTA;
        }
        return 0;
    }
}

int main()
{
    ifstream f("evaluare.in");
    char EXPR[LMAX];

    f.getline(EXPR, LMAX + 1);
    arbore* TREE = Formare(EXPR);

    ofstream g("evaluare.out");
    g << Eval(TREE);
    return 0;
}