Cod sursa(job #2139662)

Utilizator RenataRenata Renata Data 22 februarie 2018 18:08:22
Problema Evaluarea unei expresii Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 3.57 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ch
{
    int type; // 0= numar, 1=operator
    long nr; // operand sau prioritate
    char op;
};

void forma_poloneza(char s[], struct ch** fps, int *ifps)
{
    struct ch *v, *st, *fp;
    v= (struct ch*) malloc(100001 * sizeof(struct ch)); // vectorul de simboluri
    st= (struct ch*) malloc(100001 * sizeof(struct ch)); // stiva
    fp= (struct ch*) malloc(100001 * sizeof(struct ch)); // forma poloneza
    int i,j, n=0, nr=0, ist=-1, ifp=-1;

    for(i=0;i<strlen(s); i++)
    {
        if(s[i] >='0' && s[i] <='9')
        {
            nr=0;
            while(s[i] >='0' && s[i] <='9')
            {
                nr= nr*10 + (s[i]-'0');
                i++;
            }
            v[n].type = 0;
            v[n++].nr = nr;
        }

        switch(s[i]) {
            case '(':
            case ')': v[n].type = 1;
                      v[n].nr = 0;
                      v[n++].op = s[i];
                      break;
            case '*':
            case '/': v[n].type = 1;
                      v[n].nr = 1;
                      v[n++].op = s[i];
                      break;
            case '+':
            case '-': v[n].type = 1;
                      v[n].nr = 2;
                      v[n++].op = s[i];
                      break;
        }

    }


    for(i=0;i<n;i++)
    {

        if(v[i].type == 0)
            fp[++ifp] = v[i];
        else
        {
            switch(v[i].nr)
            {
                case 1: st[++ist] = v[i];
                        break;

                case 2: while(st[ist].nr ==  1 && ist>=0)
                            fp[++ifp] = st[ist--];
                        st[++ist] = v[i];
                        break;

                case 0: if(v[i].op == '(')
                           st[++ist] = v[i];
                        else
                        {
                            while(st[ist].op != '(' && ist>0)
                             fp[++ifp] = st[ist--];
                            ist--;
                        }
                        break;
            }

        }
    }


    while(ist>=0)
        fp[++ifp] = st[ist--];

    ifp++;
    (*ifps )= ifp;
    (*fps) = fp;

    /*
    for(i=0;i<ifp;i++)
    {
        if(fp[i].type == 0)
            printf("%ld ", fp[i].nr);
        else
            printf("%c ", fp[i].op);
    }*/

}

long calculeaza_expresie(struct ch fp[], int n )
{
    int i,j, ist=-1;
    struct ch *st, rez, nr1, nr2;
    rez.type = 0;
    nr1.type = 0;
    nr2.type = 0;

    st= (struct ch*) malloc(100001 * sizeof(struct ch)); // stiva

    for(i=0; i<n; i++)
    {
        if(fp[i].type == 0)
            st[++ist] = fp[i];
        else
        {
            nr2= st[ist--];
            nr1= st[ist--];

            switch(fp[i].op)
            {
                case '+': rez.nr = nr1.nr + nr2.nr; break;
                case '-': rez.nr = nr1.nr - nr2.nr; break;
                case '*': rez.nr = nr1.nr * nr2.nr; break;
                case '/': rez.nr = nr1.nr / nr2.nr; break;

            }

            st[++ist] = rez;
        }
    }

    return st[0].nr;

}

int main()
{
    struct ch *fp;
    int ifp;

    char expr[100002];

    FILE *f = fopen("evaluare.in", "r");
    fscanf(f,"%s",expr);
    fclose(f);

    forma_poloneza(expr, &fp, &ifp);
    long r = calculeaza_expresie(fp, ifp);

    FILE *g = fopen("evaluare.out", "w");
    fprintf(g,"%ld",r);
    fclose(g);

    return 0;
}