Cod sursa(job #1533736)

Utilizator jimcarterJim Carter jimcarter Data 22 noiembrie 2015 21:47:59
Problema Evaluarea unei expresii Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.65 kb
#include <cstdio>
#include <stack>
#include <cctype>
using namespace std;
FILE *f = fopen ( "evaluare.in" , "r" ) , *g = fopen ( "evaluare.out" , "w" );

struct levelType
{
    int argL , argR;
    char operation;
};
const int maxInt = 2000000000;
const levelType empty = { maxInt , maxInt , NULL };
stack <levelType> equation , toSolve;
levelType level;
char c , op , overLap;
int x , y , num;

bool isDigit ( char c ) { return isdigit ( c ); }
bool isOperator ( char c ) { return (c == '-' || c == '+' || c == '*' || c == '/'); }
bool isBracket ( char c ) { return ( c == '(' || c == ')' ); }
int priority ( char c )
{
    switch ( c )
    {
        case '(' : return 0;
        case ')' : return 0;
        case '-' : return 1;
        case '+' : return 1;
        case '*' : return 2;
        case '/' : return 2;
    }
}
int execute ( int x , char operation , int y )
{
    switch ( operation )
    {
        case '+' : return x + y;
        case '-' : return x - y;
        case '*' : return x * y;
        case '/' : return x / y;
    }
}

char getOperation()
{
    level = equation . top() , equation . pop () , op = '(';
    if ( !equation . empty() )
        op = equation . top() . operation;
    equation . push ( level );
    return op;
}

int solve()
{
	while ( !toSolve . empty() )
	{
		x = toSolve . top() . argR;
		toSolve . pop();
		if ( !toSolve . empty() )
            op = toSolve . top() . operation , y = toSolve . top() . argL , toSolve . top() . argR = execute ( x , op , y );
	}
	return x;
}

void solveTopLayers( char c , int p ) //solve layers with the same priority as p
{
	while ( !equation . empty() && priority ( getOperation() ) == p )
	{
		level = empty;
		level . argL = equation . top () . argL;
		equation . pop();
		if ( !equation . empty() )
        {
			level . operation = equation . top () . operation ;
			op = equation . top() . operation ;
			equation . top() . operation = NULL;
        }
		else
			level . argR = level . argL;
		toSolve . push ( level );
	}
	if ( !equation . empty() )
    {
        level = empty , level . argR = equation . top() . argL ;
        toSolve . push ( level ) ;
        equation . top() . operation = op;
    }
	level . argL = solve();
	if ( !equation . empty() )
        equation . pop() ;
	equation . push ( level );
}

void solveBrackets()
{
	while ( !equation.empty() && getOperation() != '(' )
	{
		op = getOperation();
		if ( op != '(' )
            solveTopLayers( op , priority( op ) );
		else
			equation . pop () , equation . push ( level );
	}
	if ( !equation.empty() )
        equation . pop() , equation . pop() , equation . push ( level );
}

int getNumber ( char c )
{
    num = c - '0';
    while ( !feof(f) && !overLap )
    {
        //read a character
        fscanf ( f , "%c" , &c );
        if ( isDigit ( c ) )
            num = num * 10 + ( c - '0' );
        else
            overLap = c;
    }
    return num;
}

void addLeftArg ( char c )
{
    num = getNumber ( c );
    if ( !equation . empty() && equation . top() . operation == '-' && equation . top() . argL == maxInt ) // negative number
        equation . top() . argL = (-1) * num , equation . top() . operation = NULL;
    else
    {
        level = empty;
        level . argL = num;
        equation . push ( level );
    }
}

void addOperator ( char c )
{
    overLap = NULL;
    if ( priority ( c ) < priority ( getOperation() ) )
        solveTopLayers ( c , priority ( getOperation() ) );
    equation . top() . operation = c;   // set the new operator
}

void addBracket ( char C )
{
    overLap = NULL;
    if ( c == '(' )
    {
        level = empty;
        level . operation = c;
        equation . push ( level );
    }
    else
        solveBrackets();
}

void processCharacter ( char c )
{
    if ( isDigit ( c ) )    //digit
        addLeftArg ( c );       //we are on a new level in the stack
    if ( isOperator ( c ) ) //operator
        addOperator ( c );      //set the current level's operator to c and create a new level
    if ( isBracket ( c ) )  //bracket
        addBracket ( c );       //create a new level with operator = c
}

void read()
{
    while ( !feof(f) && c != '\n' )
    {
        //read a character
        if ( !overLap )
            fscanf ( f , "%c" , &c );
        else
            c = overLap;
        processCharacter ( c );
    }
    while ( equation . size() > 1 )
        solveTopLayers ( getOperation() , priority( getOperation() ) );
}

int main()
{
    read();
    //print the solution
    fprintf ( g , "%d\n" , equation . top() . argL );
    return 0;
}