Cod sursa(job #1458832)

Utilizator petru.cehanCehan Petru petru.cehan Data 8 iulie 2015 15:56:33
Problema Evaluarea unei expresii Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 5.72 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 [100000001] ; // aici se afla forma postfixata

int top_s , lg_c ;

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

bool isplusminus ( char op )
{
    if ( strchr ( "+-" , op ) != 0 )
              return true ;
    return false ;
}

bool istimesdivide ( char op )
{
    if ( strchr ( "*/" , op ) != 0 )
              return true ;
    return false ;
}

struct op
{
    char symb ;
    int priority ;
} ;

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

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

char * itoa ( int n )
{
    char * ret = NULL ;
    int numChars = 0;
    // Determine if integer is negative
    bool isNegative = false;
    if (n < 0)
    {
        n = -n;
        isNegative = true;
        ++ numChars ;
    }
    // Count how much space we will need for the string
    int temp = n;
    do
    {
        ++ numChars ;
        temp /= 10 ;
    } while ( temp );
    //Allocate space for the string (1 for negative sign, 1 for each digit, and 1 for null terminator)
    ret = new char [ numChars + 1 ];
    ret [ numChars ] = 0;
    //Add the negative sign if needed
    if (isNegative) ret[0] = '-';
    // Copy digits to string in reverse order
    int i = numChars - 1;
    do
    {
        ret [ i-- ] = n%10 + '0';
        n /= 10;
    } while (n);

    return ret;
}

void ConvertToPostfix ( char sir [100000001] ) // calculez forma postfixata
{
    int i = 0  , nr ;
    char * nr_char ; // folosit pentru itoa ( a trece numarul din int in char )
    int lg = strlen ( sir ) ;

    while ( lg > 0 )
      {
          if ( isplusminus ( sir[i] ) )
             {
                  if ( top_s > 0 )
                    while ( stiva [ top_s ]. priority >= 1 )  // verific ca nu cumva in varful stivei sa fie un operator cu prioritate mai mare ( *,/ )
                             coada [ lg_c ] = stiva [ top_s ].symb , -- top_s , ++ lg_c , coada [ lg_c ] = ',' , ++ lg_c ;

                  ++ top_s , stiva [ top_s ].symb = sir[i] , stiva [ top_s ].priority = 1 , strcpy ( sir , sir + 1 ) , -- lg ;
             }
          else
              if ( istimesdivide ( sir[i] ) )
                      ++ top_s , stiva [ top_s ].symb = sir[i] , stiva [ top_s ].priority = 10 , strcpy ( sir , sir + 1 ) , -- lg ;

            else
              if ( sir [i] == '(' ) // nu e considerata operator .. ( ii pun prioritate 0 )
                 ++ top_s , stiva [ top_s ].symb = sir[i] , stiva [ top_s ].priority = 0 , strcpy ( sir , sir + 1 ) , -- lg ;

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

                         -- top_s ; // scot paranteza '('
                         strcpy ( sir , sir + 1 ) , -- lg ;
                     }
                else // este numar
                  {
                      nr = atoi ( sir ) ;
                      nr_char = itoa ( nr ) ;
                      strcpy ( sir , sir + strlen ( nr_char ) ) , lg -= strlen ( nr_char )  ;
                      for ( unsigned int i = 0 ; i < strlen (nr_char) ; ++ i )
                                  coada [ lg_c ] = nr_char [i] , ++ lg_c ;
                      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 ].symb , -- top_s , ++ lg_c , coada [ lg_c ] = ',' , ++ lg_c ;

    cout << coada << endl ;
    coada [ lg_c ] = 0 ;

}

int stv [100001] , top ; // 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

int EvaluareExpresie ( char sir [100000001] )  // Functie ce se aplica pe forma postfixata
{
    int lg = strlen (sir) ;
    int nr , aux1 , aux2 ;

    char * nr_char ; // buffer pt itoa

    int i = 0 ;
    while ( lg > 0 )
    {
         if ( isplusminus ( sir[i] ) )
             {
                 aux1 = stv [ top ] , -- top , aux2 = stv [top] , -- top ;
                 if ( sir [i] == '+' )
                       ++ top , stv [ top ] = ( aux1 += aux2 ) ;
                 else
                       ++ top , stv [ top ] = ( aux2 -= aux1 ) ;

                 strcpy ( sir , sir + 2 ) , lg -= 2 ;
             }

         else
           if ( istimesdivide ( sir[i] ) )
             {
                 aux1 = stv [ top ] , -- top , aux2 = stv [top] , -- top ;
                 if ( sir [i] == '*' )
                        ++ top , stv [ top ] = ( aux1 *= aux2 ) ;
                 else
                        ++ top , stv [ top ] = ( aux2 /= aux1 ) ;

                 strcpy ( sir , sir + 2 ) , lg -= 2 ; // sterg si operatorul comma
             }

         else // e numar
         {
             nr = atoi ( sir ) ;
             ++ top , stv [ top ] = nr ;

             nr_char = itoa ( nr ) ;

             strcpy ( sir , sir + strlen ( nr_char ) + 1 ) , lg -= strlen ( nr_char ) , -- lg  ;  // la fel sterg op comma ,
         }
     }

return stv [ top ] ;

}

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