Lab3 - Pb4

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

constexpr auto SPATIU = 5;

void citire(vector<char>& expresie)
{
    std::ifstream fin("expresie.in");
    if (fin.peek() == EOF) {
        cout << "Expresia este vida. \n";
        return;
    }

    char c;
    while (fin >> c)
        if (c == ' ')
            continue;
        else
            expresie.push_back(c);
    fin.close();
}

int precedenta(char op)
{
    if (op == '(')
        return 0;
    if (op == '+' or op == '-')
        return 1;
    if (op == '*' or op == '/')
        return 2;
    return 3;
}

void constructie(vector<char> expresie, vector<char>& formaPoloneza)
{
    std::stack<char> S;

    for (auto c : expresie)
    {
        if (isdigit(c))
            formaPoloneza.push_back(c);
        else
            if (c == '(')
                S.push(c);
            else
                if (c == ')')
                {
                    while (!S.empty() && S.top() != '(')
                    {
                        char op = S.top();
                        S.pop();
                        formaPoloneza.push_back(op);
                    }

                    if (!S.empty() && S.top() == '(')
                        S.pop();
                }
                else
                {
                    while (!S.empty() && precedenta(c) <= precedenta(S.top()))
                    {
                        char op = S.top();
                        S.pop();
                        formaPoloneza.push_back(op);
                    }
                    S.push(c);
                }
    }

    while (!S.empty())
    {
        char op = S.top();
        S.pop();
        formaPoloneza.push_back(op);
    }
}

float efectuareOperatie(float x, float y, char op)
{
    if (op == '+')
        return x + y;
    if (op == '-')
        return x - y;
    if (op == '*')
        return x * y;
    if (op == '/')
    {
        if (y != 0)
            return (float)x / y;
        else
            return FLT_MIN;
    }
}

struct NOD
{
    char info = 'N';
    NOD* st = NULL, * dr = NULL;
};

struct ARBORE
{
    NOD* radacina = new NOD;

    bool empty()
    {
        if (radacina == NULL)
            return true;
        return false;
    }

    void formareArbore(vector<char> formaPoloneza)
    {
        stack<NOD*> stiva;

        for (auto c : formaPoloneza)
            if (isdigit(c))
            {
                NOD* nou = new NOD;
                nou->info = c;
                stiva.push(nou);
            }
            else
            {
                NOD* y = stiva.top();
                stiva.pop();
                NOD* x = stiva.top();
                stiva.pop();

                NOD* op = new NOD;
                op->info = c;
                op->st = x, op->dr = y;
                stiva.push(op);
            }

        radacina = stiva.top();
        stiva.pop();
    }

    float evaluare(NOD* rez)
    {
        if (rez == NULL)
            return 0;

        if (rez->st == NULL && rez->dr == NULL)
            return (rez->info - '0');

        float x = evaluare(rez->st);
        float y = evaluare(rez->dr);
        return efectuareOperatie(x, y, rez->info);
    }

    int inaltime(NOD* rad)
    {
        if (rad == NULL)
            return -1;

        int inaltimeSt = inaltime(rad->st);
        int inaltimeDr = inaltime(rad->dr);

        return max(inaltimeSt, inaltimeDr) + 1;
    }

    void afisareNivel(NOD* rad, int nivel)
    {
        if (rad == NULL)
            return;

        if (nivel == 0)
            cout << rad->info << ' ';
        else
        {
            afisareNivel(rad->st, nivel - 1);
            afisareNivel(rad->dr, nivel - 1);
        }
    }

    void BFS()
    {
        int h = inaltime(radacina);
        for (int nivel = 0; nivel <= h; ++nivel)
            afisareNivel(radacina, nivel);
        cout << endl;
    }

    void afisareArbore(NOD* rad, int spatiu)
    {
        if (rad == NULL)
            return;
        spatiu += SPATIU;

        afisareArbore(rad->dr, spatiu);
        cout << endl;

        for (int index = SPATIU; index < spatiu; cout << ' ', ++index);

        cout << rad->info;
        afisareArbore(rad->st, spatiu);
    }

    void stergereArbore(NOD*& rad)
    {
        if (rad == NULL)
            return;

        stergereArbore(rad->st);
        stergereArbore(rad->dr);

        delete rad;
        rad = nullptr;
    }
};

void afisare(vector<char> sir)
{
    for (auto caract : sir)
        cout << caract;
    cout << endl;
}

void eliberareMemorie(vector<char>& sir)
{
    sir.clear();
    sir.shrink_to_fit();
}

int main()
{
    vector<char> expresie, formaPoloneza;
    citire(expresie);
    if (expresie.empty()) {
        return 0;
    }

    cout << "Expresia: ";
    afisare(expresie);

    constructie(expresie, formaPoloneza);
    cout << "Forma poloneza postfixata: ";
    afisare(formaPoloneza);

    ARBORE arbore;
    arbore.formareArbore(formaPoloneza);

    cout << "Arborele sintactic: \n";
    arbore.afisareArbore(arbore.radacina, 0);
    cout << endl << endl;

    cout << "Parcurgerea in latime: ";
    arbore.BFS();

    float rezultat = arbore.evaluare(arbore.radacina);
    cout << "Evaluarea expresiei: ";
    if (rezultat != FLT_MIN)
        cout << rezultat << endl;
    else
        cout << "nu se poate imparti la 0. \n";

    eliberareMemorie(expresie);
    eliberareMemorie(formaPoloneza);
    arbore.stergereArbore(arbore.radacina);

    return 0;
}