Pagini recente » Cod sursa (job #158033) | Cod sursa (job #3266508) | Cod sursa (job #2503845) | Istoria paginii runda/300saumalas/clasament | Cod sursa (job #1533729)
#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 )
{
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;
}