/*
	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 <cctype>
using namespace std;


double doOperation(char oper, double lhs, double 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);
		}
	}
}

//	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<double> & numberStack, stack<char> & operatorStack) {
	//	Pop the operator off the operator stack
	char oper = operatorStack.top();
	operatorStack.pop();
	dbg << "Popped operator: " << oper << endl;
	
	//	Pop the right hand side operand off the number-stack
	double rhs = numberStack.top();
	numberStack.pop();
	dbg << "Popped rhs: " << rhs << endl;
	
	//	Pop the left hand side operand off the number-stack
	double lhs = numberStack.top();
	numberStack.pop();
	dbg << "Popped lhs: " << lhs << endl;
					
	//	Perform the required operation...
	double result = doOperation(oper, lhs, rhs);
	//	...and push the result on the stack
	numberStack.push(result);
	dbg << "numberStack.push(" << result << ");" << endl;
}

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 double
double parseExpression(std::string const & expression) {
	stack<double> 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.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.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<double>(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.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.0;//throw runtime_error("Syntax error in the expression somewhere.");
	
	return numberStack.top();
}

int main(int argc, char * argv[]) {	
	dbg << "Starting up..." << endl;
	
	/*try {*/
		ifstream fin("evaluare.in");	
		ofstream fout("evaluare.out");	
				
		std::string expression;
		getline(fin, expression);
				
		//	Parse the expression...
		double result = parseExpression(expression);
		fout << 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;
}