Cod sursa(job #1358611)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 24 februarie 2015 18:21:17
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.83 kb
#include <cstdio>
#include <cctype>

#ifndef ONLINE_JUDGE
#include <sys/time.h>
#endif

using namespace std;

#define MAX_S 100005
#define IN_FILE "evaluare.in"
#define OUT_FILE "evaluare.out"

inline long long getTIME( ) {
    struct timeval tv;
    gettimeofday( &tv, 0 );
    return tv.tv_sec * 1000000LL + tv.tv_usec;
}
inline short priority( const char &c ) {
    if( c == '*' || c == '/')
        return 2;
    if( c == '+' || c == '-' )
        return 1;
    return 0;
}

class expr_judge {
private:
    char op[ MAX_S ];
    int pol[ MAX_S ];
    int sop, spol;
public:
    expr_judge( ) {
        sop = spol = 0;
    }
    inline void evaluate_operators( ) {
        switch( op[ sop ] ) {
        case '+':
            pol[ spol - 1 ] += pol[ spol ];
            break;
        case '-':
            pol[ spol - 1 ] -= pol[ spol ];
            break;
        case '*':
            pol[ spol - 1 ] *= pol[ spol ];
            break;
        case '/':
            pol[ spol - 1 ] /= pol[ spol ];
            break;
        }
    }
    inline int evaluate( char *s ) {
        int i;

        i = 0;
        while( s[ i ] != '\n' ) {
            if( !isdigit( s[ i ] ) ) {
                if( s[ i ] == ')' ) {
                    while( op[ sop - 1 ] != '(' ) {
                        --sop;
                        --spol;
                        evaluate_operators( );
                    }
                    --sop;
                } else if( s[ i ] == '(' || priority( s[ i ] ) > priority( op[ sop - 1 ] ) )
                    op[ sop++ ] = s[ i ];
                else {
                    do {
                        --sop;
                        --spol;
                        evaluate_operators( );
                    } while( priority( s[ i ] ) <= priority( op[ sop - 1 ] ) );
                    op[ sop++ ] = s[ i ];
                }
                ++i;
            } else {
                pol[ spol ] = 0;
                do {
                    pol[ spol ] = ( pol[ spol ] << 1 ) + ( pol[ spol ] << 3 ) + ( s[ i ] - '0' );
                    ++i;
                } while( isdigit( s[ i ] ) );
                ++spol;
            }
        }
        while( sop > 0 ) {
            --sop;
            --spol;
            evaluate_operators( );
        }
        return *pol;
    }
};
int main( ) {
    FILE *f;
    expr_judge solver;
    char s[ MAX_S ];

    f = fopen( IN_FILE, "r" );
    fgets( s, MAX_S, f );
    fclose( f );

    f = fopen( OUT_FILE, "w" );

    #ifndef ONLINE_JUDGE
    long long start = getTIME( );
    #endif // ONLINE_JUDGE

    fprintf( f, "%d\n", solver.evaluate( s ) );

    #ifndef ONLINE_JUDGE
    printf( "DURATA: %I64d microsecunde\n", getTIME( ) - start );
    #endif // ONLINE_JUDGE

    fclose( f );

    return 0;
}