Cod sursa(job #1592363)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 7 februarie 2016 15:32:54
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.61 kb
//Evaluare expresie, varianta cu Forma Poloneza inversa
//Folosesc stiva S pentru a construi sirul in forma poloneza inversa
//Folosesc un arbore binar pentru rezolvare
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("evaluare.in");
ofstream g("evaluare.out");
char V[100001];
struct el{int val; char op; bool tip;} A[100001],B[100001];
char S[100001];
int ST,QT;
struct lista{int val; char op; bool tip; lista *ls,*ld;} *Q[100001],*rad;
int prioritate(int c)
{
    int pr=0;
    if(c=='+'||c=='-') pr=1;
    if(c=='/'||c=='*') pr=2;
    return pr;
}
int EVAL(lista *p)
{
    if(p->tip==1) return p->val;
    else
    {
        int r1=EVAL(p->ls);
        int r2=EVAL(p->ld);
        int sol;
        if(p->op=='+') sol=r1+r2;
        if(p->op=='-') sol=r1-r2;
        if(p->op=='*') sol=r1*r2;
        if(p->op=='/') sol=r1/r2;
        return sol;
    }
}
int main()
{
    f>>V;
    int L=strlen(V);
    ///prelucram sirul V in sirul A, astfel incat A.tip =1 pentru operanzi, iar A.tip=0 pentru operatii
    ///Unde A.tip==1, adica unde avem un operand, vom pune in A.val, valoarea intreaga a operandului
    ///Unde A.tip==0, adica unde avem o operatie, vom pune in A.op tipul operatiei: ( ) + - * /
    int N=-1;
    for(int i=0;i<L;++i)
    {
        N++;
        if(V[i]>='0'&&V[i]<='9')
        {
            int f=0;
            while(V[i]>='0'&&V[i]<='9')
            {
                f=f*10+V[i]-48;
                i++;
            }
            i--;
            A[N].tip=1;
            A[N].val=f;
        }
        else
        {
            A[N].tip=0;
            A[N].op=V[i];
        }
    }
    int j=-1; ST=0; QT=0;
    for(int i=0;i<=N;++i)
    {
        if(A[i].tip==1)
        {
            j++;
            B[j].tip=1;
            B[j].val=A[i].val;
        }
        if(A[i].tip==0&&A[i].op=='(')
        {
            ST++;
            S[ST]=A[i].op;
        }
        if(A[i].tip==0&&A[i].op==')')
        {
            while(S[ST]!='(')
            {
                j++;
                B[j].tip=0; B[j].op=S[ST];
                ST--;
            }
            ST--;
        }
        if(A[i].tip==0&&(A[i].op=='+'||A[i].op=='-'||A[i].op=='*'||A[i].op=='/'))
        {
            if(ST==0)
            {
                ST++;
                S[ST]=A[i].op;
            }
            else
            {
                while(ST>0&&prioritate(S[ST])>=prioritate(A[i].op))
                {
                    j++;
                    B[j].tip=0; B[j].op=S[ST];
                    ST--;
                }
                ST++;
                S[ST]=A[i].op;
            }
        }
    }
    while(ST>0)
    {
        j++;
        B[j].tip=0; B[j].op=S[ST];
        ST--;
    }
    ///In acest moment am calculat sirul in forma poloneza inversa
    ///Urmeaza sa construim arborele, ne vom ajuta totusi si de o stiva, Q, in care vom retine indici din B
    for(int i=0;i<=j;++i)
    {
        if(B[i].tip)
        {
            lista *p;
            p=new lista;
            p->tip=1;
            p->val=B[i].val;
            p->ls=NULL; p->ld=NULL;
            QT++; Q[QT]=p;
        }
        else
        {
            lista *c1=Q[QT]; QT--;
            lista *c2=Q[QT]; QT--;
            lista *p;
            p=new lista;
            p->tip=0;
            p->op=B[i].op;
            p->ls=c2;
            p->ld=c1;
            QT++; Q[QT]=p;
        }
    }
    rad=Q[QT]; QT--;
    ///acum vom calcula rezultatul pe baza arborelui creat
    int Sol=EVAL(rad);
    g<<Sol<<'\n';
    return 0;
}