Cod sursa(job #604557)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 23 iulie 2011 14:41:07
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <queue>

#define LMax 100005
#define CMax 256

#define Plus 1500000000
#define Minus 1500000001
#define Multiply 1500000002
#define Divide 1500000003

using namespace std;

char Expresie[LMax];
int L, Precedenta[CMax], Code[CMax];
queue <int> RPF;
stack <char> Stack;
stack <int> Result;

bool Operator (char C)
{
    if (strchr ("+-*/", C))
    {
        return true;
    }
    return false;
}

void Read ()
{
    freopen ("evaluare.in", "r", stdin);
    scanf ("%s", &Expresie);
    L=strlen (Expresie);
    Precedenta[(int)'+']=Precedenta[(int)'-']=1;
    Precedenta[(int)'*']=Precedenta[(int)'/']=2;
    Code[(int)'+']=Plus;
    Code[(int)'-']=Minus;
    Code[(int)'*']=Multiply;
    Code[(int)'/']=Divide;
}

void BuildRPF ()
{
    for (int i=0; i<L; ++i)
    {
        if (Expresie[i]=='(')
        {
            Stack.push (Expresie[i]);
            continue;
        }
        if (Expresie[i]==')')
        {
            while (Stack.top ()!='(')
            {
                RPF.push (Code[(int)Stack.top ()]);
                Stack.pop ();
            }
            Stack.pop ();
            continue;
        }
        if (Operator (Expresie[i]))
        {
            while (!Stack.empty () and Precedenta[(int)Stack.top ()]>=Precedenta[(int)Expresie[i]])
            {
                RPF.push (Code[(int)Stack.top ()]);
                Stack.pop ();
            }
            Stack.push (Expresie[i]);
            continue;
        }
        else
        {
            int V=atoi (Expresie+i);
            RPF.push (V);
            if (V!=0)
            {
                i+=((int)log10 (V));
            }
        }
    }
    while (!Stack.empty ())
    {
        RPF.push (Code[(int)Stack.top ()]);
        Stack.pop ();
    }
}

int Execute (int V1, int V2, int Op)
{
    if (Op==Plus)
    {
        return V1+V2;
    }
    if (Op==Minus)
    {
        return V1-V2;
    }
    if (Op==Multiply)
    {
        return V1*V2;
    }
    if (Op==Divide)
    {
        return V1/V2;
    }
    return -1;
}

void Evaluate ()
{
    while (!RPF.empty ())
    {
        int X=RPF.front ();
        RPF.pop ();
        if (X==Plus or X==Minus or X==Multiply or X==Divide)
        {
            int V2=Result.top ();
            Result.pop ();
            int V1=Result.top ();
            Result.pop ();
            Result.push (Execute (V1, V2, X));
        }
        else
        {
            Result.push (X);
        }
    }
}

void Print ()
{
    freopen ("evaluare.out", "w", stdout);
    printf ("%d\n", Result.top ());
}

int main()
{
    Read ();
    BuildRPF ();
    Evaluate ();
    Print ();
    return 0;
}