/**
 * Numerics.cpp
 */
#ifndef NUMERICS
#define NUMERICS
 
#include <sstream>
#include <string>
 
using std::stringstream;
using std::string;
 
/**
 * Convenience class for enabling easy
 * conversions between strings and primitive types.
 *
 * This class is not meant to support non-primitive types,
 * but it should if target class Type has istream and ostream
 * operators overloaded.
 */
namespace Numerics{
 
	template<class T>
	class Numerical{
 
		private:
			T number;
 
		public:
			Numerical(T value = 0) : number(value){}
			Numerical(const string& arg){
				(*this)(arg);
			}
 
			/**
			 * Attempts to assign the argument value to the value
			 * of this Object's type.
			 * If the value is invalid, nothing happens.
			 */
			string operator()(const string& arg){
				stringstream ss (stringstream::in | stringstream::out);
				try{
					ss << arg;
					ss >> number;
				}catch(...){
					// currently unsupported
				}
				return ss.str();
			}
 
			/**
			 * Attempts to assign the argument value to the value of
			 * this Object's type.
			 */
			T operator()(T value){
				return (number = value);
			}
 
			/**
			 * Returns a string representation of this Object's number
			 */
			string getString(){
				stringstream ss (stringstream::in | stringstream::out);
				ss << number;
				return ss.str();
			}
 
			/**
			 * Returns a copy of this Object's number
			 */
			T getValue(){
				return number;
			}
 
			/**
			 * Extraction operator used to return the underlying value
			 * during operations assosciated with primitive types.
			 */
			operator T& (){
				return number;
			}
 
			/**
			 * const version of the above operator. Returns a copy
			 * of this Object's number.
			 */
			operator T () const{
				return number;
			}
	};
 
	/* Some meaningful typedefs for Numerical types */
	typedef Numerical<short> Short;
	typedef Numerical<unsigned short> U_Short;
	typedef Numerical<int> Integer;
	typedef Numerical<unsigned int> U_Integer;
	typedef Numerical<double> Double;
	typedef Numerical<float> Float;
	typedef Numerical<char> Byte;
	typedef Numerical<unsigned char> U_Byte;
	typedef Numerical<wchar_t> Wide_Byte;
	typedef Numerical<long int> Long;
	typedef Numerical<unsigned long int> U_Long;
 
	/* For non-standard types, like __int8, __int16, __int32, and __int64 */
	#ifdef ALLOW_NONSTANDARD_PRIMITIVE_TYPES
 
		#if (ALLOW_NONSTANDARD_PRIMITIVE_TYPES == 0x01)
			typedef Numerical < __int8 > __Int8;
			typedef Numerical < unsigned __int8 > U___Int8;
			typedef Numerical < __int16 > __Int16;
			typedef Numerical < unsigned __int16 > U___Int16;
			typedef Numerical < __int32 > __Int32;
			typedef Numerical < unsigned __int32 > U___Int32;
			typedef Numerical < __int64 > __Int64;
			typedef Numerical < unsigned __int64 > U___Int64;
		#endif
 
	#endif
}
 
#endif

 
/**
 * EquationSolver.h
 */
 
#ifndef EQUATION_SOLVER_H
#define EQUATION_SOLVER_H
 
#include <string>
#include <vector>
 
using std::string;
using std::vector;
 
namespace EquationHelper{
 
	class EquationSolver{
		private: 
			EquationSolver();
			static string doOperation(const string&, char, const string&);
			static void correctedString(string&);
			static void removeSpaces(string&);
			static string parse(const string&);
			static bool isSolvable(const string&);
			static void calculate(vector<string>&, vector<char>&, const string&);
 
		public:
			static string solve(const string&, int = 50);
	};
}
#include "EquationSolver.cpp"
 
#endif

 
/**
 * EquationSolver.cpp
 */
 
#ifdef EQUATION_SOLVER_H
 
#include <iostream>
#include <cmath>
#include <vector>
#include "Numerics.cpp"
 
using namespace EquationHelper;
using namespace Numerics;
using std::size_t;
using std::vector;
using std::string;
using std::cout;
using std::endl;
using std::ios;
 
typedef EquationSolver ES;
 
/**
 * Private constructor - does nothing.
 */
ES::EquationSolver(){}
 
/**
 * Performs the specified operation against the
 * argument strings. The operation is dependant on
 * the value of op.
 */
string ES::doOperation(const string& lhs, char op, const string& rhs){
 
	Double bdLhs = lhs;
	Double bdRhs = rhs;
	Double temp;
	switch(op){
		case '^':
			temp( pow( bdLhs, bdRhs ) );
			break;
		case '*':
			temp( bdLhs * bdRhs );
			break;
		case '/':
			temp( bdLhs / bdRhs );
			break;
		case '+':
			temp( bdLhs + bdRhs );
			break;
		case '%':
			temp( fmod(bdLhs, bdRhs) );
			break;
	}
	return temp.getString();
}
 
/**
 * Returns the string with its enclosing paranthesis
 * stripped from it.
 */
void ES::correctedString(string& arg){
 
	size_t pos1 = arg.find_first_of("(");
	size_t pos2 = arg.find_last_of(")");
 
	if(pos1 >= 0 && pos1 < arg.length() && pos2 >= 0 && pos2 <= arg.length())
		arg[pos1] = arg[pos2] = ' ';
}
 
/**
 * Remove spaces from the argument string.
 */
void ES::removeSpaces(string& argu){
 
	string temp = "";
	for(size_t i = 0; i < argu.length(); i++)
		if(argu[i] != ' ')
			temp += argu[i];	// only add non-space characters to temp
	argu = temp;
}
 
/**
 * The brains of the program.
 * Solves expressions by using recursion for complex expressions.
 */
string ES::parse(const string& param){
 
	string expression = param;
	correctedString(expression);
	removeSpaces(expression);	// Removes paranthesis and spaces from the String expression
	string finalExpression = "";	// Placeholder for the final String before values and operands are parsed
 
	bool operatorEncountered = true;	// Used to determine if the previous value encountered is an operand
	for(size_t i = 0; i < expression.length(); i++){	// for all of the characters in the String expression
		if(expression[i] == '('){	// if we encounter a left paranthesis, the value must be a nested expression
			string placeHolder = "(";	// to prevent problems determining during boolean expression-checks
			int valuesCounted = 1;		// i.e., when should we stop? When valuesCounted is 0?
			operatorEncountered = false;	// because this will evaluate to be a number, we don't want to consider
											// this char-expression to be an operand
			for(size_t j = i + 1; valuesCounted != 0; j++){	// We know that i has to be "(" and we've accounted for it, so i+1 is what we'll use
				if(expression[j] == '(')	// if we encounted a left paranthesis, increment count
					valuesCounted++;
				else if(expression[j] == ')')	// else if its a left paranthesis, decrement count
					valuesCounted--;
 
				placeHolder += expression[j];	// append the character to the expression
			}
 
			string evaluatedString = parse(placeHolder); // recursive call - evaluate the nested expression
			finalExpression += evaluatedString;	// append the evaluatedString to the finalExpression String
			i += (placeHolder.length() - 1); // the nested expression is already solved - force i to jump to non-redundant characters
		}else{
			if(expression[i] == '-' && operatorEncountered == false)	// if we encountered a minus sign and we didn't encounter any operands
																			// before it, changes the subtraction to plus a negative
				finalExpression += '+';
 
			finalExpression += expression[i];	// append the character to the expression
			if((expression[i] == '+'
			|| expression[i] == '/'
			|| expression[i] == '^'
			|| expression[i] == '*'
			|| expression[i] == '%'
			|| expression[i] == '-'))	// if we encounter a valid operand (including minus), flag operandEncountereed to be true
				operatorEncountered = true;
			else if(expression[i] != ' ')	// else if we dont encounter whitespace nor an operand, flag operand to be false
				operatorEncountered = false;
		}
	}
 
	removeSpaces(finalExpression);	// for safety measures, removing whitespace again
	string perfectExpression = "";	// I'm planning on storing a better version of the finalExpression here
 
	for(size_t i = 0; i < finalExpression.length(); i++){	// for every character in the String finalExpression
		if((i + 1) < finalExpression.length())	// to prevent overshooting the array, this measure is taken
			if(finalExpression[i] == '-' && finalExpression[i + 1] == '-')	// if there are two - chars next to each other
				i += 2;																		// ignore them.
		perfectExpression += finalExpression[i];	// append to the perfectExpression
	}
	finalExpression = perfectExpression;	// make finalExpression point to the same address as perfectExpression
 
	vector<string> totalNumbers;	// I'm planning to use this to store Number values (as Strings)
	vector<char> totalOperations;	// I'm planning to use this to store Operand values (as Characters)
	cout << finalExpression << endl;	// Technically a debug, but it adds a nice touch to the program.
 
	for(size_t i = 0; i < finalExpression.length(); i++){	// for every character in the finalExpression
		if(finalExpression[i] >= '0' && finalExpression[i] <= '9'
		|| finalExpression[i] == '-' || finalExpression[i] == '.'){	// if our character is part of a number
			string temp = "";	//
			for(size_t j = i; j < finalExpression.length(); j++){	// We're technically breaking good programming practice here--
																// I don't intend on traversing the entire String. We're breaking
																// out of this loop the moment a non-numeric character is encountered
				if(finalExpression[j] >= '0' && finalExpression[j] <= '9'
				|| finalExpression[j] == '-' || finalExpression[j] == '.'){
						temp += finalExpression[j];	// append to the temporary String
				}else break;
			}
			totalNumbers.push_back(temp);	// add our collected number to the ArrayList
			i += temp.length() == 0 ? 0 : (temp.length() - 1);	// we don't want to have redundancy, i.e.
																// if number 242 is analyzed, 242, 42 and 2 shouldn't be stored, just 242
																// so advance i past numbers already analyzed
		}else if(finalExpression[i] == '*'
			  || finalExpression[i] == '/'
			  || finalExpression[i] == '^'
			  || finalExpression[i] == '+'
			  || finalExpression[i] == '%'
			  ){	// If we run into an operand-character, store it in the operand list
			totalOperations.push_back(finalExpression[i]);
		}
	}
 
	ES::calculate(totalNumbers, totalOperations, "^");
	ES::calculate(totalNumbers, totalOperations, "*/%");
	ES::calculate(totalNumbers, totalOperations, "+");
 
	return totalNumbers[0];	// return the value remaining in the first position of the ArrayList
}
 
/**
 * Calculates the numbers in the first vector using the operands in the 2nd vector,
 * based on the expressions allowed which are determined by the string argument.
 */
void ES::calculate(vector<string>& totalNumbers, vector<char>& totalOperations, 
				   const string& arg){
 
	for(int i = 0; i < static_cast<int>(totalOperations.size()); i++){
		if( arg.find(totalOperations[i]) != arg.npos){
			totalNumbers[i] = doOperation(totalNumbers[i], totalOperations[i], totalNumbers[i + 1]);
 
			size_t oldNumberLength = totalNumbers.size();
			size_t oldOperatorLength = totalOperations.size();
			size_t nextNumberLength = oldNumberLength - 1;
			size_t nextOperatorLength = oldOperatorLength - 1;
			size_t sCount = 0;
			size_t oCount = 0;
			vector<string> temp1 ( nextNumberLength );
			vector<char> temp2 ( nextOperatorLength );
 
			for(size_t j = 0; j < oldNumberLength; j++){
				if(j != static_cast<int>(i + 1)){
					temp1[sCount++] = totalNumbers[j];
				}
				if(j != i && j < oldOperatorLength){
					temp2[oCount++] = totalOperations[j];
				}
			}
			totalNumbers = temp1;
			totalOperations = temp2;
 
			i--;
		}
	}
}
 
/**
 * Returns true if the equation is solvable (not really),
 * returns false otherwise.
 *
 * This function is truly a misnomer, because more restrictions
 * should be put in place.
 */
bool ES::isSolvable(const string& eq){
 
	int paranthesisCount = 0;	// assuming 0 paranthesis to begin with
	for(size_t i = 0; i < eq.length(); i++){	// for every char in the String eq
		if(eq[i] == '(')	// if the element is a left paranthesis
			paranthesisCount++;	// increment the paranthesisCount
		else if(eq[i] == ')')	// else if the element is a right paranthesis
			paranthesisCount--;	// decrement the paranthesisCount
 
		if(paranthesisCount < 0)	// if brackets aren't in correct order, return false
			return false;
	}
	return paranthesisCount == 0;	// return true if paranthesisCount is zero, otherwise return false
}
 
/**
 * An attempt to solve a string-expression, given
 * a precision value.
 */
string ES::solve(const string& eq, int prec){
 
	if(isSolvable(eq)){
 
		stringstream ss (stringstream::in | stringstream::out);
		cout << eq << endl;	// Prints out the equation before it is parsed
		string value;
 
		value += '(';
		value += eq;
		value += ')';
 
		ss.setf(0, ios::floatfield);
		ss.precision(prec);
		ss << parse(value);
 
		return ss.str(); //	returning the final value of the expression
	}else return "";
}
 
#endif

 
/**
 * DriverProgram.cpp
 */
 
/****************************************
 * @Author: Mark Alexander Edwards Jr.
 *
 * This program uses a utility class to solve
 * complex equations represented by string 
 * expressions
 ****************************************/
#include <iostream>
#include <ctime>
#include <string>
#include "Numerics.cpp"
#include "EquationSolver.h"
 
using std::cin;
using std::cout;
using std::endl;
using std::flush;
using std::string;
using namespace Numerics;
using namespace EquationHelper;
 
int main(){
 
	cout << ES::solve("5 + 3 * (8 - 4)") << endl << endl;
	cout << ES::solve("12 / (3 * 4) + 5") << endl << endl;
 
	while(true){
		cout << "Enter an equation you would \nlike to solve (enter 'exit' to quit): " << flush;
		try{
			string temp;
			getline(cin, temp);
			clock_t t1 = clock();
			if(temp.compare("exit") == 0) exit(0);
			cout << "Answer: " + ES::solve(temp, 4) << endl;
			clock_t t2 = clock();
			cout << "\nTime taken to calculate value: " <<
				(t2-t1) << " Clock cycles" <<endl;
		}catch(...){
			cout << "Invalid expression! Please try again!" << endl;
		}
	}
 
	cin.ignore();
	cin.get();
	return 0;
}