Cod sursa(job #1459184)

Utilizator petru.cehanCehan Petru petru.cehan Data 9 iulie 2015 12:19:26
Problema Evaluarea unei expresii Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 3.48 kb
// Se aduce expresia la forma poloneza ( postfixata )
// Se evalueaza noua expresie

#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

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


char coada [100001] ; // aici se afla forma postfixata
char expresie [100001] ; // aici se afla forma infixata ( normala )
char  stiva [100001] ; // stiva de operatori si paranteze ( parantezele nu sunt operatori )

int  lg_c = -1 ;

int prioritate ( char op )
{
      if ( op == '(' ) return 0 ;
      if ( op == '+' ) return 1 ;
      if ( op == '-' ) return 1 ;
      if ( op == '/' ) return 2 ;
      if ( op == '*' ) return 2 ;
      if ( op == ')' ) return 4 ;
      return -1 ;
}


void Citire ()
{
    fin.getline ( expresie , 100001 ) ;
}

bool isoperator ( char c )
{
    return ( c == '+' || c == '-' || c == '*' || c == '/' ) ;
}

void ConvertToPostfix ( char expresie [100001] ) // calculez forma postfixata
{
    int i = 0 ;
    int  vf = 0 , ok , p ;

    int lg = strlen ( expresie ) ;

    while ( i < lg )
     {
         ok = 0 ;
         while ( expresie [i] >= '0' && expresie [i] <= '9' )

                   coada [ ++ lg_c ] = expresie [ i ] , ++ i , ok = 1 ;

         if ( ok ) coada [ ++ lg_c ] = ',' ;
         else
           {
              p = prioritate ( expresie[i] ) ;
              if ( p == 0 ) stiva [ ++ vf ] = expresie [ i ] , ++ i ;

              else if ( p == 4 )
               {
                  while ( stiva [vf] != '(' && vf )
                      coada [ ++ lg_c ] = stiva [ vf ] , -- vf , coada [ ++ lg_c ] = ',' ;

                 ++ i , -- vf ;
               }

                   else
                   {
                       while ( vf && p <= prioritate ( stiva [ vf ] ) )
                              coada [ ++ lg_c ] = stiva [ vf ] , -- vf , coada [ ++ lg_c ] = ',' ;

                       stiva [ ++ vf ] = expresie [ i ] , ++ i ;
                   }
        }
    }

    while ( vf )
       coada [ ++ lg_c ] = stiva [ vf ] , -- vf , coada [ ++ lg_c ] = ',' ;

}

long stv [100001] ; // aici pun operanzii
// Cand un operator este intalnit scot de pe stiva ultimii 2 operanzi , aplic operatorul intre ei si rezultatul este pus in varful stivei

long EvaluareExpresie ( char sir [100001] )  // Functie ce se aplica pe forma postfixata
{
    long b , a , vf = 1 ;
    int i = 0 , lg = strlen ( sir ) ;

    for ( i = 0 ; i < lg ; )
       if ( sir [i] >= '0' && sir [i] <= '9' )

           {
               stv [ vf ] = atol ( sir + i ) , ++ vf ;
               while ( sir [i] >= '0' && sir [i]<='9')
                                    ++ i ;
            ++ i ; // scap de comma
           }

       else
       {
           if ( isoperator( sir [i] ) == true )
            {

                  b = stv [ -- vf ] ; a = stv [ -- vf ] ;

                  switch ( sir [i] )
                   {
                    case '+' : stv [ vf ] = a + b ; break ;
                    case '-' : stv [ vf ] = a - b ; break ;
                    case '*' : stv [ vf ] = a * b ; break ;
                    case '/' : stv [ vf ] = a / b ; break ;
                   }

                 ++ vf;
            }
            i += 2 ;  // sar peste operator si peste comma
       }

return stv [1];

}


int main()
{
    Citire () ;
    ConvertToPostfix ( expresie ) ;
    fout << EvaluareExpresie ( coada ) ;
    return 0;
}