Cod sursa(job #1459166)

Utilizator petru.cehanCehan Petru petru.cehan Data 9 iulie 2015 11:48:22
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.95 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

int top_s , lg_c ;

char expresie [100001] ; // aici se afla forma infixata ( normala )

int priority ( char op )
{
    if ( op == '+' || op == '-' )
          return 1 ;

    if ( op == '*' || op == '/' )
          return 2 ;

    if ( op == ')' || op == '(' )
          return 0 ;

    return -1 ;

}

char  stiva [100001] ; // stiva de operatori si paranteze ( parantezele nu sunt operatori )

void Citire ()
{
    char c ;
    int l = 0 ;

    while ( fin >> c )
      expresie [l] = c , ++ l ;

    expresie [l] = 0 ;
}

bool isoperator ( char c )
{
    return ( strchr ( "+-/*" , c ) != 0 ) ;
}

void ConvertToPostfix ( char sir [100001] ) // calculez forma postfixata
{
    while ( *sir != '\0' )
      {
          if ( isoperator ( *sir ) )
             {
                  if ( top_s > 0 )
                    while ( priority ( stiva [ top_s ] ) >= priority ( *sir ) )  // verific ca nu cumva in varful stivei sa fie un operator cu prioritate mai mare
                             coada [ lg_c ] = stiva [ top_s ] , -- top_s , ++ lg_c , coada [ lg_c ] = ',' , ++ lg_c ;

                  ++ top_s , stiva [ top_s ] = *sir , strcpy ( sir , sir + 1 ) ;
             }
            else
              if ( *sir == '(' ) // nu e considerata operator .. ( ii pun prioritate 0 )
                 ++ top_s , stiva [ top_s ] = *sir , strcpy ( sir , sir + 1 ) ;

              else
                if ( *sir == ')' )
                     {
                         while ( stiva [ top_s ] != '(' )
                             coada [ lg_c ] = stiva [ top_s ] , -- top_s , ++ lg_c , coada [ lg_c ] = ',' , ++ lg_c ;

                         -- top_s ; // scot paranteza '('
                         strcpy ( sir , sir + 1 ) ;
                     }
                else // este numar
                  {
                      while ( *sir >= '0' && *sir <= '9' )
                                  coada [ lg_c ] = *sir , ++ lg_c , strcpy ( sir , sir + 1 ) ;
                      coada [ lg_c ] = ',' , ++ lg_c ;

                  }

      }

    while ( top_s > 0 )  // daca au mai ramas operatori pe stiva ii scot si ii adaug la coada ( la forma postfixata )
        coada [ lg_c ] = stiva [ top_s ] , -- top_s , ++ lg_c , coada [ lg_c ] = ',' , ++ lg_c ;

    coada [ lg_c ] = 0 ;

}

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 ;
    unsigned long i ;

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

           {
               stv [ vf++ ] = atol ( sir + i ) ;
                    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;
}