Pagini recente » Cod sursa (job #3216484) | Cod sursa (job #1592363)
//Evaluare expresie, varianta cu Forma Poloneza inversa
//Folosesc stiva S pentru a construi sirul in forma poloneza inversa
//Folosesc un arbore binar pentru rezolvare
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("evaluare.in");
ofstream g("evaluare.out");
char V[100001];
struct el{int val; char op; bool tip;} A[100001],B[100001];
char S[100001];
int ST,QT;
struct lista{int val; char op; bool tip; lista *ls,*ld;} *Q[100001],*rad;
int prioritate(int c)
{
int pr=0;
if(c=='+'||c=='-') pr=1;
if(c=='/'||c=='*') pr=2;
return pr;
}
int EVAL(lista *p)
{
if(p->tip==1) return p->val;
else
{
int r1=EVAL(p->ls);
int r2=EVAL(p->ld);
int sol;
if(p->op=='+') sol=r1+r2;
if(p->op=='-') sol=r1-r2;
if(p->op=='*') sol=r1*r2;
if(p->op=='/') sol=r1/r2;
return sol;
}
}
int main()
{
f>>V;
int L=strlen(V);
///prelucram sirul V in sirul A, astfel incat A.tip =1 pentru operanzi, iar A.tip=0 pentru operatii
///Unde A.tip==1, adica unde avem un operand, vom pune in A.val, valoarea intreaga a operandului
///Unde A.tip==0, adica unde avem o operatie, vom pune in A.op tipul operatiei: ( ) + - * /
int N=-1;
for(int i=0;i<L;++i)
{
N++;
if(V[i]>='0'&&V[i]<='9')
{
int f=0;
while(V[i]>='0'&&V[i]<='9')
{
f=f*10+V[i]-48;
i++;
}
i--;
A[N].tip=1;
A[N].val=f;
}
else
{
A[N].tip=0;
A[N].op=V[i];
}
}
int j=-1; ST=0; QT=0;
for(int i=0;i<=N;++i)
{
if(A[i].tip==1)
{
j++;
B[j].tip=1;
B[j].val=A[i].val;
}
if(A[i].tip==0&&A[i].op=='(')
{
ST++;
S[ST]=A[i].op;
}
if(A[i].tip==0&&A[i].op==')')
{
while(S[ST]!='(')
{
j++;
B[j].tip=0; B[j].op=S[ST];
ST--;
}
ST--;
}
if(A[i].tip==0&&(A[i].op=='+'||A[i].op=='-'||A[i].op=='*'||A[i].op=='/'))
{
if(ST==0)
{
ST++;
S[ST]=A[i].op;
}
else
{
while(ST>0&&prioritate(S[ST])>=prioritate(A[i].op))
{
j++;
B[j].tip=0; B[j].op=S[ST];
ST--;
}
ST++;
S[ST]=A[i].op;
}
}
}
while(ST>0)
{
j++;
B[j].tip=0; B[j].op=S[ST];
ST--;
}
///In acest moment am calculat sirul in forma poloneza inversa
///Urmeaza sa construim arborele, ne vom ajuta totusi si de o stiva, Q, in care vom retine indici din B
for(int i=0;i<=j;++i)
{
if(B[i].tip)
{
lista *p;
p=new lista;
p->tip=1;
p->val=B[i].val;
p->ls=NULL; p->ld=NULL;
QT++; Q[QT]=p;
}
else
{
lista *c1=Q[QT]; QT--;
lista *c2=Q[QT]; QT--;
lista *p;
p=new lista;
p->tip=0;
p->op=B[i].op;
p->ls=c2;
p->ld=c1;
QT++; Q[QT]=p;
}
}
rad=Q[QT]; QT--;
///acum vom calcula rezultatul pe baza arborelui creat
int Sol=EVAL(rad);
g<<Sol<<'\n';
return 0;
}