Mai intai trebuie sa te autentifici.
Cod sursa(job #1459184)
Utilizator | 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;
}