Cod sursa(job #2811364)

Utilizator tester.11tester tester.11 Data 1 decembrie 2021 22:33:41
Problema Evaluarea unei expresii Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.9 kb
#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

    unsigned 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 foorma
        //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;
}