Pagini recente » Cod sursa (job #1459395) | Cod sursa (job #1485817) | Cod sursa (job #716458) | Cod sursa (job #2805386) | Cod sursa (job #550367)
Cod sursa(job #550367)
//Parcurgem expresia tinand cont de nivelurile subexpresiilor
//si de nivelurile de prioritate a operatorilor
#include<stdio.h>
#include<string.h>
#define NMAX 1<<17
#define LMAX 2
FILE *in,*out;
char op[4][4] = { "+-", "*/", "^", "" };
char S[NMAX],*p;
/*
In fiecare nod al arborelui, vom retine o valoare (in cazul frunzeolor)
sau un operator (in cazul nodurilor interne), si doi pointeri catre
fii stang, respectiv drept ai nodului
Constructorul seteaza toti membrii cu valoarea nula
*A este un pointer catre radacina arborelui
*/
typedef struct node
{
int val;
char op;
node *l,*r;
node(int a=0,char b=0,node *c=0,node *d=0):
val(a),op(b),l(c),r(d) {}
};
node *A;
/*
Urmatoarea functie evalueaza expresia care incepe pe pozitie indicata de p
considerand ca aceasta este de nivel lev
Daca am ajuns pe ultimul nivel, studiem cele doua cazuri pentru E(L) :
* poate urma o expresie de nivel 0 intre paranteze: (E(0))
* poate urma o constanta (pentru alte probleme si o variabila)
In primul caz, trecem peste '(', evaluam E(0) si trecem peste ')'.
In cel de-al doilea caz, citim numarul, cifra cu cifra
Daca nu suntem pe ultimul nivel, vom evalua expresia
E1(lev+1) op(lev) E2(lev+1) op(lev)...
Initial, x va fi E1(lev+1), apoi, la al i-ulea operator op(lev) intalnit
x = E1(lev+1) op(lev) ... op(lev) Ei(lev+1)
y = x op(lev) E_i+1_(lev+1)
Cand trimitem parametrii functiei eval, pointerul p este incrementat
inainte de apelul recursiv
*/
node *expr(int lev)
{
node *x,*y;
if(lev==LMAX)
if(*p=='(')
{
p++;
x=expr(0);
p++;
}
else
for(x=new node; *p>='0' && *p<='9';p++)
x->val = 10*x->val + *p - '0';
else
for(x=expr(lev+1);strchr(op[lev],*p);x=y)
y= new node(0,*p++,x,expr(lev+1));
return x;
}
int eval( node *n ) {
switch( n->op ) {
case '+': return eval( n->l ) + eval( n->r );
case '-': return eval( n->l ) - eval( n->r );
case '*': return eval( n->l ) * eval( n->r );
case '/': return eval( n->l ) / eval( n->r );
default: return n->val;
}
}
int main()
{
in=fopen("fp.in","rt");
out=fopen("fp.out","wt");
fscanf(in,"%s",S);
S[strlen(S)]='\n';
p=S;
A=expr(0);
fclose(in);
fprintf(out,"%d\n",eval(A));
return 0;
}