Pagini recente » Cod sursa (job #1413385) | Cod sursa (job #1213432) | Cod sursa (job #1032552) | Cod sursa (job #348176) | Cod sursa (job #3276375)
#include <bits/stdc++.h>
#define dim 100005
using namespace std;
stack <char> st;//pentru obtinerea formei poloneze
stack <int> stiva;//pentru calcularea expresiei
char sir[dim];
char forma[dim][11];
int sf=-1;//tine indicele liniei din forma
char operatori[]="+-/*";
//prioritatea cea mai mare o au parantezele, apoi operatorii de multiplicare si apoi cei aditivi
int prioritate(char c)
{
if(c=='/' or c=='*')
return 2;
if(c=='+' or c=='-')
return 1;
return 0;
}
int main()
{
ifstream fin("evaluare.in");
ofstream fout("evaluare.out");
fin.get(sir,dim);
//construim forma poloneza in matricea forma (fiecare linie retine cate un element)
//ma folosesc de stiva st pentru a retine operatorii si parantezele rotunde deschise
//parcurg sirul si aplic algoritmul de constructie al formei poloneze postfixate
int i=0;
while(sir[i]!=0)
{
//daca este numar, il adaug la forma;
if(sir[i]>='0' and sir[i]<='9')
{
char numar[11];
int j=0;
while(sir[i]>='0' and sir[i]<='9')
{
numar[j]=sir[i];
j++;
i++;
}
numar[j]=0;
++sf;
strcpy(forma[sf],numar);
}
//daca este paranteza rotunda deschisa, adaug in stiva
else if(sir[i]=='(')
{
st.push(sir[i]);
i++;
}
//daca este paranteza rotunda dreapta, extrag toti operatorii din stiva pana la ( si ii copii in forma
else if(sir[i]==')')
{
char c=st.top();
while(c!='(')
{
++sf;
forma[sf][0]=c;
forma[sf][1]=0;
st.pop();
c=st.top();
}
st.pop();//elimin din stiva paranteza rotunda
i++;
}
//daca este operator, se extrag din stiva toti operatorii cu prioritate egala sau mai mare
//se adauga la forma
//se adauga in stiva operatorul curent
else if(strchr(operatori,sir[i]))
{
int p=prioritate(sir[i]);
//verific si daca stiva nu e goala, ca sa evit o bucla infinita
while(!st.empty() and prioritate(st.top())>=p and strchr(operatori,st.top()))
{
++sf;
forma[sf][0]=st.top();
forma[sf][1]=0;
st.pop();
}
st.push(sir[i]);
i++;
}
}
//eventualii operatori ramasi in stiva ii mut in forma
while(!st.empty())
{
++sf;
forma[sf][0]=st.top();
forma[sf][1]=0;
st.pop();
}
//afisez forma
// for(i=0;i<=sf;i++)
// fout<<forma[i]<<" ";
//evaluez expresia folosind forma poloneza din matricea forma
for(i=0;i<=sf;i++)
{
//daca linia i contine un numar(sub forma de vector de charuri),il transform la numar si adaug in stiva
if(forma[i][0]>='0' and forma[i][0]<='9')
{
int nr=0,j=0;
while(forma[i][j]!=0)
{
nr=nr*10+(forma[i][j]-'0');
j++;
}
stiva.push(nr);
}
//daca este operator, se evalueaza primii 2 termeni din varful stivei
//rezultatul se adauga in stiva
else
{
int a,b;
a=stiva.top();
stiva.pop();
b=stiva.top();
stiva.pop();
int c;
if(forma[i][0]=='+')
c=b+a;
if(forma[i][0]=='-')
c=b-a;
if(forma[i][0]=='*')
c=b*a;
if(forma[i][0]=='/')
c=b/a;
stiva.push(c);
}
}
fout<<stiva.top();
return 0;
}