Pagini recente » Cod sursa (job #1244749) | Cod sursa (job #1736272) | Cod sursa (job #559639) | Cod sursa (job #11136) | Cod sursa (job #218981)
Cod sursa(job #218981)
#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;
}