Pagini recente » Cod sursa (job #735010) | Romanian IOI Medalists: Careers | Cod sursa (job #1131872) | Istoria paginii runda/concurs_11_12_02_26 | Cod sursa (job #1459166)
// 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;
}