/*
	Author's name: Alin Tomescu
	Website: http://alinush.isgreat.org
	Date: 8:38 AM Friday, April 24, 2009
	File: Core.h
*/

#define NDEBUG

#ifdef NDEBUG
#define dbg	0 && (*((ostream *) 0))
#else
#define dbg clog
#endif

#include <iostream>
#include <fstream>
#include <string>
#include <iterator>
#include <algorithm>
#include <stack>
#include <stdexcept>
#include <map>

#include <cmath>
#include <cctype>
using namespace std;


long doOperation(char oper, long lhs, long rhs) {
	switch(oper) {
		case '-': return lhs-rhs;
		case '+': return lhs+rhs;
		case '*': return lhs*rhs;
		case '/': return lhs/rhs;
		default: 
		{
			//std::string message("Invalid operator: \'");
			//message += oper;
			//message += "\' was passed to doOperation()";
			//dbg << "Exception thrown!" << endl;
			//throw invalid_argument(message);
			return 0;
		}
	}
}

//	Pops the operator from the operator-stack and applies it to the two operands at the top of the number-stack, which are popped...
//	Then pushes the result on the number-stack.
void computeNextInStack(stack<long> & numberStack, stack<char> & operatorStack) {
	//	Pop the operator off the operator stack
	char oper = operatorStack.top();
	operatorStack.pop();
	
	//	Pop the right hand side operand off the number-stack
	long rhs = numberStack.top();
	numberStack.pop();
	
	//	Pop the left hand side operand off the number-stack
	long lhs = numberStack.top();
	numberStack.pop();
					
	//	Perform the required operation...
	long result = doOperation(oper, lhs, rhs);
	//	...and push the result on the stack
	numberStack.push(result);
}

unsigned int priority(char op) {
	switch(op) {
		case '+':
		case '-':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return 0;
	}
}

//	Parses the expression, returning the result as a long
long parseExpression(std::string const & expression) {
	stack<long> numberStack;	//	Numbers will be pushed here...
	stack<char> operatorStack;	//	Operators such as +.-,*,/, and ( will be pushed on this stack
	
	//	Get an std::string::iterator to the begining of the expression string...
	std::string::const_iterator pos = expression.begin();
	
	//	Parse the string, char by char...	
	while(pos != expression.end()) {
		//	Get the current character...
		char current = *pos;
		
		switch(current) {
			//	If it's an operator then...			
			case '-':
			case '+':
			case '*':
			case '/':
			{
				//	If there are other operators with higher precedence/priority than the current operator
				//	Then pop each one of them, applying them to the next two numbers in the number-stack
				//	And push the result on the stack
				//	\--> This means calling computeNextInStack()
				while(
					!operatorStack.empty() && 
					priority(operatorStack.top()) >= priority(current))
				{
					computeNextInStack(numberStack, operatorStack);
				}
				
				//	After all the higher priority operators have been evaluated, we can now push the current, lower-priority operator on the stack				
				operatorStack.push(current);
				break;
			}
			//	If it's an opening parenthesis, just push it on the stack, the ')' case will handle the rest...
			case '(':
				operatorStack.push(current);
				break;
			//	If it's a closing parenthesis...
			case ')':
			{
				//	Make sure there are operators in the operator stack...
				//	Otherwise there was a syntax error...
				if(operatorStack.empty())
					return 0;//throw runtime_error("Syntax error in expression. No matching \'(\' found.");
					
				//	After that, until you reach the opening parenthesis, keep calculating the expression in the stack...
				while(operatorStack.top() != '(') {
					computeNextInStack(numberStack, operatorStack);
					
					//	If the operators were exhausted, that means there was no opening parenthesis...
					//	So we throw a syntax error exception...
					if(operatorStack.empty())
						return 0;//throw runtime_error("Syntax error in expression. No matching \'(\' found.");
				}
				
				//	If the loop finished execution, then an opening parenthesis was found, and we need to pop it off the stack...
				operatorStack.pop();
				break;
			}
			//	If it's any other character....
			default:
			{
				//	And that character happens to be a digit...
				if(isdigit(current)) {
					//	Then we parse the number...
					long number = 0;
					while(pos != expression.end() && isdigit(*pos)) {
						number *= 10;
						number += *pos - '0';
						pos++;
					}
					
					//	And then push it on the stack...
					numberStack.push(static_cast<long>(number));					
					
					//	We also decrement the position by one step, because it's going to be advanced below, in the while loop
					pos--;
				
				//	If it's not a number, then it's an invalid character, so we just skip it...
				} else {
					//dbg << "Invalid character encountered: \'" << current << "\', skipping..." << endl;
				}
				break;
			}
		}
		pos++;
	}
	
	//	The two stack will always have operators and operands left on them, because the loop only computes part of the expression
	//	Specifically, the loop handles sub-expressions such as 1*4 + 3 transforming them into 7 + 3
	//	The 7+3 will then be computed here...
	
	//	Add up remaining operators...		
	while(!operatorStack.empty()) {
		char oper = operatorStack.top();
		if(oper == '(')
			return 0;//throw runtime_error("Syntax error in expression. No matching \')\' found.");
		
		computeNextInStack(numberStack, operatorStack);
	}
	
	//	The number stack should now have only one element in it: The final result...
	if(numberStack.size() != 1)
		return 0;//throw runtime_error("Syntax error in the expression somewhere.");
	
	return numberStack.top();
}

void parseFromStdin() {
	std::string expression;
	
	do {
		cout << "Enter a correct expression	 	:\n\t> ";
		getline(cin, expression);
		
		//	Parse the expression...
		long result = parseExpression(expression);
		cout << "Expression: " << expression;
		cout << " is equal to " << round(result) << endl;
		
		cout << endl;
	} while(!expression.empty());
}

void parseFromInFiles(int argc, char * argv[]) {
	char okFile[64];
	std::string expression;
	
	for(int i = 1; i < argc; i++) {
		memset(okFile, 0, 64);
		strncpy(okFile, argv[i], strlen(argv[i])-3);
		cout << okFile << endl;
		strcat(okFile, ".ok");
		cout << "In: " << argv[i] << "\nOk: " << okFile << "\n\n";
				
		ifstream fin(argv[i]);		
		getline(fin, expression);
		long result = static_cast<long>(round(parseExpression(expression)));
		
		ifstream finOk(okFile);
		long goodResult;
		finOk >> goodResult;
		
		cout << "Yours: " << result << " - Theirs: " << goodResult << endl;
		if(result != goodResult)
			cout << "Fail #" << i << endl;
		
		fin.close();
		finOk.close();
	}
}

int main(int argc, char * argv[]) {	
	dbg << "Starting up..." << endl;
	
	// if(argc > 1)
		// parseFromInFiles(argc, argv);
	// else
		// parseFromStdin();
	
	/*try {*/
		ifstream fin("evaluare.in");	
		ofstream fout("evaluare.out");	
				
		std::string expression;
		getline(fin, expression);
				
		//	Parse the expression...
		long result = parseExpression(expression);
		fout << round(result);
		
		fin.close();
		fout.close();
	/*} catch(const exception& e) {
		cout << "Exception occurred: " << e.what() << endl;
		return -1;
	} catch(...) {
		cout << "Unhandled exception!" << endl;
		return -1;
	}*/
	
	dbg << "Exiting normally..." << endl;
	return 0;
}