/*problema evaluare de pe infoarena, evaluarea unei expresii aritmetice
reprezentam expresia cu un arbore binar folosit ptr forma poloneza,
unde operatorii sunt pe noduri interioare, iar operanzii pe frunze
evit recursivitatea indirecta si folosesc metoda cu prioritati ale operatorilor
Definesc 3 nivele de prioritati:
- nivelul 0 ptr operatorii +-
- nivelul 1 ptr operatorii * /
- nivelul 2 - nivelul de operanzi sau, eventual, reluare de la nivelul 0

O expresie de nivel k va fi definita astfel

E(k)=E(k+1) op(k) E(k+1) op(k)...op(k) E(k+1), k=0,1, unde E(k+1) este expresie de nivel k+1, iar op(k) operator de nivel k
E(2)=(E(0)) sau operand
Atunci cand ajung la nivelul 2, fie dau de un operand, fie de o paranteza rotunda deschisa. Daca este rotunda deschisa,
atunci expresia din paranteze este una noua ce trebuie evaluata de la nivelul 0
Cand suntem de nivelele 0 sau 1, implementarea recurentei se face din aproape in aproape, cu ajutorul a doua noduri x si y
Initial x va retine prima expresie E(k+1).
Apoi y va retine pe rand nodul rezultat in urma expresiei x op(k) cu urmatoarea expresie de nivel k+1

Arborele va fi retinut dinamic, fiecare nod avand informatia (operand sau operator) si doua campuri de adresa,
ptr fiul stang si ptr cel drept.
Limita de valori ptr operanzi este 1 000 000 000
vom lua 1 000 000 001 ca fiind +, 1 000 000 002, drept -, 1 000 000 003 *, 1 000 000 004 /

Alegerea nodului curent din arbore se va face dupa tehnica cu prioritati prezentata mai sus

Functia va intoarce nodul astfel construit, prn urmare, in final, va returna adresa radacinii arborelui
Daca vrem forma poloneza prefixata a expresiei, vom folosi o parcurgere radacina stanga dreapta, iar daca vrem cea postfixata,
stanga dreapta radacina

Evaluarea expresiei se va face tot dupa tehnica Divide et Impera
    Daca nodul nu este terminal se retine valoarea returnata de apelul cu fiul stang si cea rezultata de la fiul drept
    si apoi se aplica operatorul continut de csmpul informatie
    contrar, se intoarce operandul


*/
#include <fstream>
#include <cstring>

#define dim 100005

#define plus 1000000001
#define minus 1000000002
#define ori 1000000003
#define div 1000000004

using namespace std;

char sir[dim],*p;

struct nod
{
    int info;
    nod* stg;
    nod *drp;
};
//matrice ce retine operatorii pe nivele
char op[2][3]={"+-","*/"};
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

nod *generare(int k)
{
    nod* x, *y;
        if(k==2)
        {
            if(*p=='(')
            {
                //sar peste paranteza rotunda deschisa, retin in x apelul de la nivelul 0 si sar peste paranteza rotunda inchisa
                ++p;
                x=generare(0);
                ++p;
            }
            else
            {
                //am un operand, creez un nod nou si completez
                x=new nod;
                for(x->info=0;*p>='0' && *p<='9';p++)
                    x->info=(x->info)*10+(*p-'0');
                x->stg=0;
                x->drp=0;
            }
        }
        else
        {
            for(x=generare(k+1);strchr(op[k],*p)&& (*p)!=0;x=y)
            {
                y=new nod;
                //vad ce operator voi scrie in campul info
                switch (*p)
                {
                    case '+':y->info=plus;break;
                    case '-':y->info=minus;break;
                    case '*':y->info=ori;break;
                    case '/':y->info=div;break;
                }
                //in stanga voi retine nodul x
                y->stg=x;
                //ne mutam la urmatorul caracter si in dreapta expresia urmatoare de nivel k+1
                p++;
                y->drp=generare(k+1);
            }
        }
        return x;
}

int evaluare(nod*rad)
{
    switch(rad->info)
    {
        case plus: return evaluare(rad->stg)+evaluare(rad->drp);break;
        case minus: return evaluare(rad->stg)-evaluare(rad->drp);break;
        case ori: return evaluare(rad->stg)*evaluare(rad->drp);break;
        case div: return evaluare(rad->stg)/evaluare(rad->drp);break;
        default: return rad->info;
    }
}

void sdr(nod* r)
{
    if(r!=NULL)
    {
        sdr(r->stg);
        sdr(r->drp);
        fout<<r->info<<" ";
    }
}

int main()
{
    fin.get(sir, dim);
    p=sir;
    nod*rad=generare(0);
    fout<<evaluare(rad);
    return 0;
}