Cod sursa(job #218778)

Utilizator mika17Mihai Alex Ionescu mika17 Data 3 noiembrie 2008 16:10:57
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.59 kb
#include <fstream>

#define fin "evaluare.in"
#define fout "evaluare.out"
#define NMAX 100002

using namespace std;

ifstream f(fin);
ofstream g(fout);

char e[NMAX],prio[256];

struct nod
{
 int v; char o; nod * l, * r;
};

template < class T >
struct stiva
{
 T data[NMAX];
 int size;
};


void creaza_nod(stiva <nod*> & st,stiva <char> & op)
{
 nod * p = new nod;

 p->v = 0; //nod intern
 p->o = op.data [ op.size -- ];
 p->r = st.data [ st.size -- ];  //operatii necomutative
 p->l = st.data [ st.size -- ];

 st.data[ ++st.size ] = p;
}

void creaza_frunza(stiva <nod*> & st,int info)
{
 nod * p = new nod;
 
 p->v = info; p->o = 0; p->l = p->r = NULL;

 st.data[ ++st.size ] = p;
}

nod * constr_arb()
{
        stiva < nod * > st;
        stiva < char > op;
        st.size = op.size = -1;

        for(int i = 0; e[i] && e[i] != '\n'; ++i)
        {
                if(e[i] == '(')
                  op.data[ ++op.size ] = e[i];

                else
                 if(e[i] == '*' || e[i] == '+' || e[i] == '-' || e[i] == '/')
                 {
                  if (e[i] == '-' && (!i || e[i-1] == '(') ) // '-' unar
                  {
                   creaza_frunza(st,0);
                  }
                   
                  if( op.size != -1 && op.data [ op.size ] != '(')

                   while(prio[ e[i] ] <= prio[ op.data[ op.size ] ])

                      creaza_nod(st,op); //nod intern

                  op.data[ ++op.size ] = e[i];

                 }
                else
                 if(e[i] == ')')
                 {
                  while( op.data [ op.size ] != '(')
                    creaza_nod(st,op);

                  --op.size; //pop '('
                 }

                 else
                 {
                   int v = 0;
                   while(e[i] >= '0' && e[i] <= '9')
                    v = v * 10 + e[i++] - '0';

                   --i; creaza_frunza(st,v);
                 }
        }
        
        while(op.size != -1)
          creaza_nod(st,op);
         
        return st.data[st.size --]; //radacina

}

int eval(nod * p)
{
 switch(p->o)
 {
  case '+': return eval(p->l) + eval(p->r);
  case '-': return eval(p->l) - eval(p->r);
  case '*': return eval(p->l) * eval(p->r);
  case '/': return eval(p->l) / eval(p->r);
  default : return p->v;
 }
}

int main()
{
        f.read(e,NMAX);

        prio['/'] = prio['*'] = 2;
        prio['+'] = prio['-'] = 1;

        nod * rad = constr_arb();

        g<<eval(rad);

        return 0;
}