Cod sursa(job #1327484)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 26 ianuarie 2015 19:29:56
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.08 kb
#include <fstream>
#include <cstring>
#define nmax 100005
#define inf 0x3f3f3f3f
#define par_deschisa inf+1
#define par_inchisa inf+2
#define plus inf+3
#define minus inf+4
#define ori inf+5
#define impartit inf+6

using namespace std;

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");

char s[nmax];
int a[nmax],b[nmax],st[nmax],vf,n,n2;

int prioritate(int k)
{
    if(k==plus||k==minus)
        return 0;
    if(k==ori||k==impartit)
        return 1;
    return -1;
}

void citire()
{
    fin>>s;
    int nr=strlen(s);
    for(int i=0;i<nr;i++)
    {
        if(s[i]=='(')
            a[++n]=par_deschisa;
        else
        if(s[i]==')')
            a[++n]=par_inchisa;
        else
        if(s[i]=='+')
            a[++n]=plus;
        else
        if(s[i]=='-')
            a[++n]=minus;
        else
        if(s[i]=='*')
            a[++n]=ori;
        else
        if(s[i]=='/')
            a[++n]=impartit;
        else
        {
            if(a[n]<inf&&n>0)
                a[n]=a[n]*10+(s[i]-'0');
            else
                a[++n]=s[i]-'0';
        }
    }
}

void forma_poloneza()
{
    a[0]=par_deschisa;
    a[++n]=par_inchisa;
    for(int i=0;i<=n;i++)
    {
        if(a[i]==par_deschisa)
            st[++vf]=par_deschisa;
        else
        if(a[i]<inf)
            b[++n2]=a[i];
        else
        if(a[i]==par_inchisa)
        {
            while(st[vf]!=par_deschisa)
                b[++n2]=st[vf--];
            vf--;
        }
        else
        {
            while(prioritate(a[i])<=prioritate(st[vf]))
                b[++n2]=st[vf--];
            st[++vf]=a[i];
        }
    }
}

void evaluare()
{
    int x,y;
    for(int i=1;i<=n2;i++)
    {
        if(b[i]==plus)
        {
            x=st[vf--];
            if(vf)
                y=st[vf--];
            else
                y=st[vf];
            st[++vf]=x+y;
        }
        else
        if(b[i]==minus)
        {
            x=st[vf--];
            if(vf)
                y=st[vf--];
            else
                y=st[vf];
            st[++vf]=y-x;
        }
        else
        if(b[i]==ori)
        {
            x=st[vf--];
            y=st[vf--];
            st[++vf]=x*y;
        }
        else
        if(b[i]==impartit)
        {
            x=st[vf--];
            y=st[vf--];
            st[++vf]=y/x;
        }
        else
            st[++vf]=b[i];
    }
}

void afisare()
{
    fout<<st[vf]<<"\n";
    /*
    for(int i=1;i<=n2;i++)
    {
        if(b[i]==par_deschisa)
            fout<<"(";
        else
        if(b[i]==par_inchisa)
            fout<<")";
        else
        if(b[i]==plus)
            fout<<"+";
        else
        if(b[i]==minus)
            fout<<"-";
        else
        if(b[i]==ori)
            fout<<"*";
        else
        if(b[i]==impartit)
            fout<<"/";
        else
            fout<<b[i];
    }
    */
}

int main()
{
    citire();
    forma_poloneza();
    evaluare();
    afisare();
    return 0;
}