#ifndef __MATH_EXPRESSION__
#define __MATH_EXPRESSION__

#include <string>

class MathExpression
{
public:
	MathExpression(std::string expression);

	virtual ~MathExpression();

	virtual std::string GetInfixExpression();
	virtual std::string GetPrefixExpression();
	virtual std::string GetPostfixExpression();

	virtual int Evaluate();

protected:

	struct ExpressionNode
	{
		bool isOperand;
		int data;
		ExpressionNode* left;
		ExpressionNode* right;
		ExpressionNode(bool isOperand = true, int data = 0, ExpressionNode* left = NULL, ExpressionNode* right = NULL)
		{
			this->data = data;
			this->isOperand = isOperand;
			this->left = left;
			this->right = right;
		}
	};

	ExpressionNode* _root;

private:

	static int EvaluateNode(ExpressionNode *node);
	static void DeleteNode(ExpressionNode *node);
	/*
	Gramatica : 
	E -> T ([+-]T)*
	T -> F ([/*]F)*
	F -> (E) | NR
	NR -> [1-9]+[0-9]*|0
	*/

	static ExpressionNode* ParseExpression(std::string& expression, unsigned int& index);
	static ExpressionNode* ParseTermen(std::string& expression, unsigned int& index);
	static ExpressionNode* ParseFactor(std::string& expression, unsigned int& index);
};


#endif/*__MATH_EXPRESSION__*/


#include <stack>
#include <list>


//#define  __MATH_EXPRESSION_RECURSIVE__
#define __MATH_EXPRESSION_ITERATIVE__

#if defined  __MATH_EXPRESSION_RECURSIVE__ && defined __MATH_EXPRESSION_ITERATIVE__ 
#error <MathExpression> __MATH_EXPRESSION_RECURSIVE__ and __MATH_EXPRESSION_ITERATIVE__ both defined !
#elif !defined  __MATH_EXPRESSION_RECURSIVE__ && !defined __MATH_EXPRESSION_ITERATIVE__ 
#error <MathExpression> __MATH_EXPRESSION_RECURSIVE__ and __MATH_EXPRESSION_ITERATIVE__ none defined !
#endif

MathExpression::MathExpression(std::string expression)
{
	unsigned int index = 0;
	this->_root = ParseExpression(expression, index);
	
}

MathExpression::~MathExpression()
{
	DeleteNode(this->_root);
}

void MathExpression::DeleteNode(ExpressionNode* node)
{


#ifdef __MATH_EXPRESSION_RECURSIVE__
	if( !node->isOperand)
	{
		DeleteNode(node->left);
		DeleteNode(node->right);
	}
	delete node;
#else

#endif
}

std::string MathExpression::GetInfixExpression()
{
	return std::string();
}

std::string MathExpression::GetPrefixExpression()
{
	return std::string();
}

std::string MathExpression::GetPostfixExpression()
{
	return std::string();
}

int MathExpression::Evaluate()
{	
	return EvaluateNode(this->_root);
}

MathExpression::ExpressionNode* MathExpression::ParseExpression(std::string &expression, unsigned int & index)
{
	ExpressionNode *termen = ParseTermen(expression, index);
	ExpressionNode *nextTermen;
	while(expression[index] == '+' || expression[index] == '-')
	{
		char currentOp = expression[index];
		index++;
		nextTermen = ParseTermen(expression, index);
		termen = new ExpressionNode(false, currentOp, termen, nextTermen);
	}
	return termen;
}

MathExpression::ExpressionNode* MathExpression::ParseTermen(std::string &expression, unsigned int & index)
{
	ExpressionNode *factor = ParseFactor(expression, index);
	ExpressionNode *nextFactor;
	while(expression[index] == '*' || expression[index] == '/')
	{
		char currentOp = expression[index];
		index++;
		nextFactor = ParseFactor(expression, index);
		factor = new ExpressionNode(false, currentOp, factor, nextFactor);
	}
	return factor;
}

MathExpression::ExpressionNode* MathExpression::ParseFactor(std::string &expression, unsigned int & index)
{
	ExpressionNode *expr;
	if(expression[index] == '(')
	{
		index++;
		expr = ParseExpression(expression, index);
		index++;
	}
	else
	{
		int terminal = 0;
		while( '0' <= expression[index] && expression[index] <= '9')
		{
			terminal *= 10;
			terminal += expression[index] - '0';
			index++;
		}

		expr =  new ExpressionNode(true, terminal);
	}
	return expr;
}


int MathExpression::EvaluateNode(ExpressionNode* node)
{
#ifdef __MATH_EXPRESSION_RECURSIVE__
	if(node->isOperand)
	{
		return node->data;
	}
	else
	{
		switch(node->data)
		{
		case '+': return EvaluateNode(node->left) + EvaluateNode(node->right);
		case '-': return EvaluateNode(node->left) - EvaluateNode(node->right);
		case '*': return EvaluateNode(node->left) * EvaluateNode(node->right);
		case '/': return EvaluateNode(node->left) / EvaluateNode(node->right);
		}
	}

	return 0;
#else

	std::list<ExpressionNode*> postOrder;
	std::list<ExpressionNode*>::iterator itr2;
	postOrder.push_back(node);

	for(std::list<ExpressionNode*>::iterator itr = postOrder.begin();
		itr != postOrder.end(); itr++)
	{
		if( (*itr)->isOperand == false)
		{
			std::list<ExpressionNode*>::iterator itr2;
			itr2 = itr; itr2++;
			postOrder.insert(itr2, (*itr)->right); 
			itr2 = itr; itr2++;
			postOrder.insert(itr2, (*itr)->left);
		}
	}
	std::stack<int> stivaNumere;
	for(std::list<ExpressionNode*>::reverse_iterator itr = postOrder.rbegin();
		itr != postOrder.rend(); itr++)
	{
		if((*itr)->isOperand)
		{
			stivaNumere.push((*itr)->data);
		}
		else
		{
			int numar1 = stivaNumere.top(); stivaNumere.pop();
			int numar2 = stivaNumere.top(); stivaNumere.pop();
			switch((*itr)->data)
			{
			case'+': numar1 += numar2; break;
			case'-': numar1 -= numar2; break;
			case'*': numar1 *= numar2; break;
			case'/': numar1 /= numar2; break;
			}
			stivaNumere.push(numar1);
		}
	}
	return stivaNumere.top();
#endif
}





#ifdef __DEBUG__
#define _CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>
#endif

#include <fstream>

using namespace std;

const unsigned int BUFFER_SIZE = 200001;

const char infile[] = "evaluare.in";
const char outfile[] = "evaluare.out";

char buffer[BUFFER_SIZE];

int main(int argc, char* argv[])
{
#ifdef __DEBUG__
	{
#endif

	fstream fin(infile, ios::in);
	fin.read(buffer, BUFFER_SIZE);
	fin.close();
	
	MathExpression expr(buffer);
	
	fstream fout(outfile, ios::out);

	fout << expr.Evaluate() << "\n";

	fout.close();

#ifdef __DEBUG__
	}
	_CrtDumpMemoryLeaks();
#endif 
}