Pagini recente » Cod sursa (job #1722482) | Cod sursa (job #2799974) | Cod sursa (job #2162519) | Cod sursa (job #1903874) | Cod sursa (job #218778)
Cod sursa(job #218778)
#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;
}