// 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;
}