Cod sursa(job #477633)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 15 august 2010 17:38:47
Problema Evaluarea unei expresii Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.04 kb
/* Rezolvare folosind recursivitatea indirecta (transformare RPN) si evaluarea expresiei RPN
** Autor : Cosmina Albulescu (miculprogramator)
** IDE : Code :: Blocks
*/
#include <stdio.h>
#include <string.h>
using namespace std;

char e[100001];
int prior[20], rpn[100001], used[100001], stack[10001];
int lg, i, k;
int varf;

void transformare_expresie ();      // transforma expresia in RPN
void transformare_termen ();        // transforma termenul in RPN
void transformare_factor ();        // transforma factorul in RPN

int e_operator (char ch)
{
    if (ch >= '0' && ch <= '9')
        return 1;
    return 0;
}

void initializare ()
{
    prior['+'] = prior['-'] = 1;
    prior['*'] = prior['/'] = 2;
}

void transformare_factor ()
{
    if (e[i] == '(')
    {
        i ++;                         // trec peste (
        transformare_expresie ();     // evaluez expresia dintre ( )
        i ++;                         // trec peste )
    }
    else
    {
        k ++;
        while (e_operator (e[i]))
        {
            rpn[k] = rpn[k] * 10 + e[i] - '0';      // introduc factorul in rpn
            i ++;               // trec la urmatorul factor
        }
    }
}

void transformare_termen ()
{
    int ch;
    transformare_factor ();     // transform primul factor

    while (i < lg && prior[e[i]] == 2)     // cat timp mai urmeaza factori
    {
        ch = e[i];                         // retin semnul (* sau /)
        i ++;
        transformare_factor ();             // trec la factorii urmatori
        k ++;
        rpn[k] = ch;
        used[k] = 1;
    }
}

void transformare_expresie ()
{
    int ch;
    transformare_termen ();     // transform primul termen

    while (i < lg && prior[e[i]] == 1)      //cat timp mai am termeni
    {
        ch = e[i];                          // retin semnul (+ sau -)
        i ++;
        transformare_termen ();             // trec la termenii urmatori
        k ++;
        rpn[k] = ch;
        used[k] = 1;
    }
}

void afisare_rpn ()
{
    for (i=1; i<=k; ++i)
        if (used[i])
            printf ("%c ", rpn[i]);
        else
            printf ("%d ", rpn[i]);
}

int main ()
{
    FILE *f = fopen ("evaluare.in","r");
    FILE *g = fopen ("evaluare.out","w");
    fscanf (f,"%s", e);
    lg = strlen (e);

    initializare ();
    transformare_expresie ();
    //afisare_rpn ();

    i = 1;
    while (i <= k)      // evaluam RPN
    {
        if (used[i])
        {
            if (rpn[i] == '+')
                stack[varf-1] += stack[varf];
            if (rpn[i] == '-')
                stack[varf-1] -= stack[varf];
            if (rpn[i] == '*')
                stack[varf-1] *= stack[varf];
            if (rpn[i] == '/')
                stack[varf-1] /= stack[varf];
            varf --;
        }
        else
        {
            varf ++;
            stack[varf] = rpn[i];
        }
        i ++;
    }

    fprintf (g, "%d", stack[1]);

    fclose (g);
    fclose (f);
    return 0;
}