Cod sursa(job #218981)

Utilizator mika17Mihai Alex Ionescu mika17 Data 4 noiembrie 2008 17:04:56
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.66 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 vf;

 stiva ()
 {
  vf = -1;
 }

 T top()
 {
  return data[vf];
 }

 void push(T info)
 {
  data[++vf] = info;
 }

 T pop()
 {
  return data[vf--];
 }

 bool isempty()
 {
  return (vf == -1);
 }
};


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

 p->v = 0; //nod intern
 p->o = op.pop();
 p->r = st.pop();  //operatii necomutative
 p->l = st.pop();

 return p;
}

nod * creaza_frunza(int info)
{
 nod * p = new nod;
 
 p->v = info; p->o = 0; p->l = p->r = NULL;

 return p;
}

nod * constr_arb()
{
        stiva < nod * > st;
        stiva < char > op;

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

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

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

                     st.push( creaza_nod(st,op) ); //nod intern

                  op.push( e[i] );

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

                  op.pop(); //pop '('
                 }

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

                   --i; st.push( creaza_frunza(v) );
                 }
        }
        
        while( !op.isempty() )
          st.push( creaza_nod(st,op) );
         
        return st.pop(); //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;
}