Cod sursa(job #1592222)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 7 februarie 2016 12:07:09
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.23 kb
//Se construieste sirul b, reprezentat forma poloneza inversa a sirului a
//folosim o stiva pentru ajutor, stiva S, cu elemente char
//Rezolvam apoi sirul B, folosind stiva Q cu elemente int
//Datorita existentei numerelor cu mai mult de o cifra, voi transforma elementele char din a, in elemente int
//din B, codificand operatiile astfel:
// + = -99990
// - = -99991
// * = -99992
// / = -99993
//Codificarea este necesara
#include<fstream>
#include<stack>
#include<string.h>
using namespace std;
ifstream f("exp.in");
ofstream g("exp.out");
char A[100001];
int B[100001];
stack<char> S;
stack<int> Q;
int prioritate(int c)
{
    int pr=0;
    if(c=='+'||c=='-') pr=1;
    if(c=='/'||c=='*') pr=2;
    return pr;
}
int main()
{
    f>>A;
    int L=strlen(A);
    int i=0,j=-1;
    for(int i=0;i<L;++i)
    {
        if(A[i]>='0'&&A[i]<='9')
        {
            int f=0;
            while(A[i]>='0'&&A[i]<='9')
            {
                f=f*10+A[i]-48;
                i++;
            }
            j++; B[j]=f;
        }
        if(A[i]=='(')
        {
            S.push(A[i]);
        }
        if(A[i]==')')
        {
            while(S.top()!='(')
            {
                j++;
                if(S.top()=='+') B[j]=-99990;
                if(S.top()=='-') B[j]=-99991;
                if(S.top()=='*') B[j]=-99992;
                if(S.top()=='/') B[j]=-99993;
                S.pop();
            }
            S.pop();
        }
        if(A[i]=='+'||A[i]=='-'||A[i]=='*'||A[i]=='/')
        {
            if(S.empty())
            {
                S.push(A[i]);
            }
            else
            {
                while(!S.empty()&&prioritate(S.top())>prioritate(A[i]))
                {
                    j++;
                    if(S.top()=='+') B[j]=-99990;
                    if(S.top()=='-') B[j]=-99991;
                    if(S.top()=='*') B[j]=-99992;
                    if(S.top()=='/') B[j]=-99993;
                    S.pop();
                }
                S.push(A[i]);
            }
        }
    }
    while(!S.empty())
    {
        j++;
        if(S.top()=='+') B[j]=-99990;
        if(S.top()=='-') B[j]=-99991;
        if(S.top()=='*') B[j]=-99992;
        if(S.top()=='/') B[j]=-99993;
        S.pop();
    }
   // for(int i=0;i<=j;++i) g<<B[i]<<" ";
  //  g<<'\n';
    ///acum avand scrisa expresia in forma poloneza inversa (postfix), rezolvam expresia mai usor
    for(int i=0;i<=j;++i)
    {
        if(B[i]==-99990)
        {
            int a=Q.top(); Q.pop();
            int b=Q.top(); Q.pop();
            Q.push(a+b);
        }
        if(B[i]==-99991)
        {
            int a=Q.top(); Q.pop();
            int b=Q.top(); Q.pop();
            Q.push(b-a);
        }
        if(B[i]==-99992)
        {
            int a=Q.top(); Q.pop();
            int b=Q.top(); Q.pop();
            Q.push(a*b);
        }
        if(B[i]==-99993)
        {
            int a=Q.top(); Q.pop();
            int b=Q.top(); Q.pop();
            Q.push(b/a);
        }
        if(B[i]!=-99990&&B[i]!=-99991&&B[i]!=-99992&&B[i]!=-99993)
        {
            Q.push(B[i]);
        }
    }
    g<<Q.top()<<'\n';
    return 0;
}