Cod sursa(job #1081006)

Utilizator bflorin97Bardas Florin bflorin97 Data 13 ianuarie 2014 07:49:30
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include<string>
#include<cstdio>
#include<cstdlib>
#define maxv 1000000000
using namespace std;

struct NOD
{
    long double op;
    NOD *as,*ad;
};

long double e[100001],efp[100001];
long int pfp[100001],p[100001],n;

NOD *c;

NOD *arb(int li,int ls,long double efp[100001],long int pfp[100001])
{
    NOD* c;
    int i,j;
    long double cmin;
    cmin=pfp[ls];
    i=ls;
    for(j=ls;j>=li;j--)
        if(pfp[j]<cmin)
        {
            cmin=pfp[j];
            i=j;
        }
    c = new NOD;
    c->op=efp[i];
    if(li==ls)
    {
        c->as=0;
        c->ad=0;
    }
    else
    {
        c->as=arb(li,i-1,efp,pfp);
        c->ad=arb(i+1,ls,efp,pfp);
    }
    return c;
}

long double parc(NOD *c)
{
    if(c)
    {
        long double a,b;
        a=parc(c->as);
        b=parc(c->ad);
        if(c->op == maxv+3)
            return a+b;
        if(c->op == maxv+4)
            return a-b;
        if(c->op == maxv+5)
            return a*b;
        if(c->op == maxv+6)
            return a/b;
        return c->op;
    }
}

int main()
{
    int i,j;
    char s[100001];
    ifstream f("evaluare.in");
    ofstream g("evaluare.out");
    f.getline(s,100001);
    long nr=0;
    n=0;
    for(i=0;i<strlen(s);i++)
    {
        if(s[i]=='(' || s[i]==')' || s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/')
        {
            if(nr)
            {
                e[++n]=nr;
                nr = 0;
            }
            if(s[i]=='(')
                e[++n]=maxv+1;
            if(s[i]==')')
                e[++n]=maxv+2;
            if(s[i]=='+')
                e[++n]=maxv+3;
            if(s[i]=='-')
                e[++n]=maxv+4;
            if(s[i]=='*')
                e[++n]=maxv+5;
            if(s[i]=='/')
                e[++n]=maxv+6;
        }
        else nr=nr*10+(s[i]-'0');
    }
    if(nr)
        e[++n]=nr;
    j=0;
    for(int i=1;i<=n;i++)
    {
        if(e[i]==maxv+5 || e[i]==maxv+6)
            p[i]=j+10;
        else if(e[i]==maxv+3 || e[i]==maxv+4)
            p[i]=j+1;
        else if(e[i]==maxv+1)
            j+=10;
        else if(e[i]==maxv+2)
            j-=10;
        else p[i]=j+10000;
    }
    j=1;
    for(i=1;i<=n;i++)
    if(e[i]!=maxv+1 && e[i]!=maxv+2)
    {
        efp[j]=e[i];
        pfp[j]=p[i];
        j++;
    }
    c=arb(1,j-1,efp,pfp);
    cout<<parc(c);
    return 0;
}