Cod sursa(job #1214246)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 29 iulie 2014 21:30:11
Problema Evaluarea unei expresii Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.86 kb
//varianta cu arbori, sursa mare (approx. 4kb) si tot felul de codificari
#include <fstream>
#include <cstring>
#include <vector>
#define MX 100005
using namespace std;
// -1=+, -2=-, -3=*, -4=/

ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
int l;
char s[MX];
vector<char> inf;  //infix si stack
vector<int> pof;    //postfix si rezultatul final

struct nod
{
    int info;
    nod *left, *right;
}*prim;
vector<nod*> rez;

void citire()
{
    fin>>s;
    l = strlen(s);
}

int numar(int &i)
{
    int nr=0;
    while(s[i]>='0' && s[i]<='9')
    {
        nr = nr*10 + s[i] - '0';
        i++;
    }
    i--;
    return nr;
}

void infix_to_postfix()
{
    int i;
    char x;
    for(i=0; i<l; i++)
    {
        if(s[i]=='*' || s[i]=='/')
        {
            inf.push_back(s[i]);
        }
        else

        if(s[i]=='+' || s[i]=='-')
        {
            if(!inf.empty())
            {
                x = inf.back();
                while(x=='*' || x=='/')
                {
                    inf.pop_back();
                    //pof.push_back(x);
                    if(x == '*') pof.push_back(-3);
                    else pof.push_back(-4);
                    x = inf.back();
                }
            }
            inf.push_back(s[i]);
        }
        else

        if(s[i]=='(')
        {
            inf.push_back(s[i]);
        }
        else

        if(s[i]==')')
        {
            x = inf.back();
            while(x != '(')
            {
                inf.pop_back();
                //pof.push_back(x);
                if(x == '+') pof.push_back(-1);
                if(x == '-') pof.push_back(-2);
                if(x == '*') pof.push_back(-3);
                if(x == '/') pof.push_back(-4);
                x = inf.back();
            }
            inf.pop_back();
        }
        else
        {
            pof.push_back(numar(i));
        }

        /*fout<<i;
        fout.flush();*/
    }

    while(!inf.empty())
    {
        //pof.push_back(inf.back());
        x = inf.back();
        if(x == '+') pof.push_back(-1);
        if(x == '-') pof.push_back(-2);
        if(x == '*') pof.push_back(-3);
        if(x == '/') pof.push_back(-4);
        inf.pop_back();
    }

    //fout<<pof[5];
}

void postfix_to_rez()
{
    l = pof.size();
    nod *p, *op1, *op2;
    vector<int>::iterator it;
    for(it=pof.begin(); it!=pof.end(); it++)
    {
        if(*it >= 0)
        {
            p = new nod;
            p->info = *it;
            p->left = NULL;
            p->right = NULL;
            rez.push_back(p);
        }
        else
        {
            op1 = rez.back(); rez.pop_back();
            op2 = rez.back(); rez.pop_back();
            p = new nod;
            p->info = *it;
            p->left = op2;
            p->right = op1;
            rez.push_back(p);
        }
    }

    //prim = p;
}

void SDR(nod* p)
{
    if(p != NULL)
    {
        SDR(p->left);
        SDR(p->right);
        //fout<<p->info<<' ';
        delete p;
    }
}

int suma(nod *p)
{
    if(p == NULL) return 0;
    else
    {
        if(p->info >= 0) return p->info;
        else
        {
            switch(p->info)
            {
                case -1: return( suma(p->left) + suma(p->right) ); break;
                case -2: return( suma(p->left) - suma(p->right) ); break;
                case -3: return( suma(p->left) * suma(p->right) ); break;
                case -4: return( suma(p->left) / suma(p->right) ); break;
            }
        }
    }
}

int main()
{
    citire();
    infix_to_postfix(); //inf e gol, pof are postfix
    postfix_to_rez();

    prim = rez[0];
    rez.clear();
    pof.clear();

    fout<<suma(prim);
    SDR(prim);

    fin.close(); fout.close();
    return 0;
}