Cod sursa(job #593238)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 iunie 2011 20:34:16
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.92 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <cstring>

#define Plus -1000000005
#define Minus -1000000006
#define Multiply -1000000007
#define Divide -1000000008

using namespace std;

char Expresie[100005];
deque <char> Stiva;
deque <long> RPF;
deque <long> Result;
int Precedenta[255];

void Read ()
{
    ifstream fin ("evaluare.in");
    fin.get (Expresie, 100001, '\n');
    fin.close ();
}

void Type ()
{
    ofstream fout ("evaluare.out");
    fout << Result[0] << "\n";
    fout.close ();
}

void CreareFP ()
{
    long i, L, V;
    Precedenta[(int)'+']=1;
    Precedenta[(int)'-']=1;
    Precedenta[(int)'*']=2;
    Precedenta[(int)'/']=2;
    L=strlen (Expresie);
    for (i=0; i<L; i++)
    {
        if (Expresie[i]=='(')
        {
            Stiva.push_back ('(');
            continue;
        }
        if (Expresie[i]==')')
        {
            while (Stiva[Stiva.size ()-1]!='(')
            {
                switch (Stiva[Stiva.size ()-1])
                {
                    case '+': RPF.push_back (Plus);
                              break;
                    case '-': RPF.push_back (Minus);
                              break;
                    case '*': RPF.push_back (Multiply);
                              break;
                    case '/': RPF.push_back (Divide);
                              break;
                    default : break;
                }
                Stiva.pop_back ();
            }
            Stiva.pop_back ();
            continue;
        }
        if (strchr ("+-*/", Expresie[i])!=0)
        {
            if (Stiva.size ()==0)
            {
                Stiva.push_back (Expresie[i]);
                continue;
            }
            if (Precedenta[(int)Stiva[Stiva.size ()-1]]<Precedenta[(int)Expresie[i]])
            {
                Stiva.push_back (Expresie[i]);
                continue;
            }
            while ((Stiva.size ()>0)&&(Precedenta[(int)Stiva[Stiva.size ()-1]]>=Precedenta[(int)Expresie[i]]))
            {
                switch (Stiva[Stiva.size ()-1])
                {
                    case '+': RPF.push_back (Plus);
                              break;
                    case '-': RPF.push_back (Minus);
                              break;
                    case '*': RPF.push_back (Multiply);
                              break;
                    case '/': RPF.push_back (Divide);
                              break;
                    default : break;
                }
                Stiva.pop_back ();
            }
            Stiva.push_back (Expresie[i]);
            continue;
        }
        V=0;
        while (((int)Expresie[i]-(int)'0'>=0)&&((int)Expresie[i]-(int)'0'<=9))
        {
            V*=10;
            V+=((int)Expresie[i]-(int)'0');
            i++;
        }
        i--;
        RPF.push_back (V);
    }
    while (Stiva.size ()>0)
    {
        switch (Stiva[Stiva.size ()-1])
        {
            case '+': RPF.push_back (Plus);
                      break;
            case '-': RPF.push_back (Minus);
                      break;
            case '*': RPF.push_back (Multiply);
                      break;
            case '/': RPF.push_back (Divide);
                      break;
            default : break;
        }
        Stiva.pop_back ();
    }
}

void EvaluareFP ()
{
    long V1, V2;
    while (RPF.size ()>0)
    {
        switch (RPF[0])
        {
            case Plus     : V1=Result[Result.size ()-1];
                            Result.pop_back ();
                            V2=Result[Result.size ()-1];
                            Result.pop_back ();
                            Result.push_back (V2+V1);
                            break;
            case Minus    : V1=Result[Result.size ()-1];
                            Result.pop_back ();
                            V2=Result[Result.size ()-1];
                            Result.pop_back ();
                            Result.push_back (V2-V1);
                            break;
            case Multiply : V1=Result[Result.size ()-1];
                            Result.pop_back ();
                            V2=Result[Result.size ()-1];
                            Result.pop_back ();
                            Result.push_back (V2*V1);
                            break;
            case Divide   : V1=Result[Result.size ()-1];
                            Result.pop_back ();
                            V2=Result[Result.size ()-1];
                            Result.pop_back ();
                            Result.push_back (V2/V1);
                            break;
            default       : Result.push_back (RPF[0]);
                            break;
        }
        RPF.pop_front ();
    }
}

int main()
{
    Read ();
    CreareFP ();
    EvaluareFP ();
    Type ();
    return 0;
}