Cod sursa(job #2539425)

Utilizator octavi26octavian octavi26 Data 5 februarie 2020 20:52:00
Problema Evaluarea unei expresii Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.07 kb
#include <bits/stdc++.h>
#define N 105

using namespace std;

ifstream fin ("evaluare.in");
ofstream fout ("evaluare.out");

char s[N]; ///expresie aritmetrica
char polon[N]; ///forma poloneza
char operatori[]="+-*/%";
char operanzi[26];

int f[158];

int Inv( int x )
{
    int nr=0;
    while( x )
    {
        nr=nr*10+(x%10);
        x/=10;
    }
    return nr;
}

int Numar( int j )
{
    int i=0, x;
    int nr=0;
    char aux[N];
    x=s[j];
    if( s[j]>='0' && s[j]<='9' )
    {
        nr=nr*10+(s[j]-'0');
        j++;
    }
    while( s[j]>='0' && s[j]<='9' )
    {
        nr=nr*10+(s[j]-'0');
        strcpy(aux, s+j+1);
        strcpy(s+j, aux);
    }
    //f[i]=Inv( f[i] );
    if( x>='0' && x<='9' ) j--;
    for( i=97; i<=122; i++ )
    {
        if( f[i]==nr && x>='0' && x<='9' ) { f[i]=nr; s[j]=i; return j; }
        if( f[i]==0 && x>='0' && x<='9' ) { f[i]=nr; s[j]=i; return j; }
    }
    for( i=65; i<=90; i++ )
    {
        if( f[i]==nr && x>='0' && x<='9' ) { f[i]=nr; s[j]=i; return j; }
        if( f[i]==0 && x>='0' && x<='9' ) { f[i]=nr; s[j]=i; return j; }
    }
    return j;
}

void Citire()
{
    fin>>s;
    fin.close();
    int m=strlen(s);
    int i=0;
    while( i<m )
    {
        i=Numar(i);
        i++;
    }
}

inline bool Prioritate(char c)
{
    if (c=='+' || c=='-') return 0;
    return 1;
}

void FormaPoloneza(char s[])
{
    int n=strlen(s);
    int i;
    int p1, p2;
    char oper[N]; ///stiva operatorilor
    int no=-1, np=-1; ///stivele sunt vide initial
    for (i=0; i<n; ++i)
        if (isalpha(s[i])) polon[++np]=s[i]; ///adaugam operanzi in stiva polon
        else if (s[i]=='(') oper[++no]=s[i]; ///adaugam paranteza deschisa in oper
            else if (s[i]==')')
                {
                    while (oper[no]!='(') polon[++np]=oper[no--]; ///adaugam in polon toti operatorii pana la '('
                    no--;
                }
                else ///avem operator
                    if (no==-1) oper[++no]=s[i]; ///adaugam operatorul in stiva
                    else if (oper[no]=='(') oper[++no]=s[i]; ///daca avem paranteza adaugam operatorul
                        else
                        {
                            p1=Prioritate(s[i]);
                            p2=Prioritate(oper[no]);
                            if (p1<p2) ///daca avem operator cu prioritate mai mica realizam toate operatii mai mari
                            {
                                while (no>=0 && oper[no]!='(' && p1<p2) polon[++np]=oper[no--], p2=Prioritate(oper[no]);
                                oper[++no]=s[i];
                            }
                            else if (p1==p2) ///daca au aceeasi prioritat operatiile se efectueaza de la stanga la dreapta
                                {
                                    polon[++np]=oper[no--];
                                    oper[++no]=s[i];
                                }
                                else oper[++no]=s[i]; ///daca are prioritate mai mare il adaugam
                        }
    while (no>=0) polon[++np]=oper[no--]; ///la final mutam toti operatorii ramasi in polon
    polon[++np]=0;
    //fout<<polon;
}

int EvaluareExpresie(char polon[])
{
    int val[N], i;
    char aux[N];
    int n=strlen(polon);
    for (i=0; i<n; ++i)
    if (isalpha(polon[i])) val[i]=f[polon[i]];
    else val[i]=-1;
    while (n>1)
    {///cautam primul opertor
    i=0;
        while (isalpha(polon[i])) i++;
        if (polon[i]=='+') val[i-2]=val[i-2]+val[i-1];
        if (polon[i]=='-') val[i-2]=val[i-2]-val[i-1];
        if (polon[i]=='*') val[i-2]=val[i-2]*val[i-1];
        if (polon[i]=='/') val[i-2]=val[i-2]/val[i-1];
        if (polon[i]=='%') val[i-2]=val[i-2]%val[i-1];
        strcpy(aux, polon+i+1);
        strcpy(polon+i-1, aux);
        for (int j=i-1; j<n-1; ++j)
        val[j]=val[j+2];
        n-=2;
    }
    return val[0];
}

int main()
{
    Citire();
    FormaPoloneza(s);
    fout<<EvaluareExpresie(polon);
    return 0;
}