// Reverse Polish Notation Calculator
// February 23rd 2010
// Created By Nic Raboy

#include <iostream>
#include <string.h>
#include <stack>
#include <math.h>

using namespace std;

// Remove all space characters from the user input math formula
// It is much easier to solve a formula if it is linearly formatted
string trimspaces(string str)
{
	for(int i = 0; i <= str.length(); i++)
	{
		if(str[i] == ' ')
		{
			str.erase(i, 1);
		}
	}
	return str;
}

// Convert the numbers from their initial string format to double
double strtodouble(string str)
{
	return atof(str.c_str());
}

// After math is done on our doubles, the solved number must be re-added
// back to the stack of values in string format.  This function will convert the double
// back into a string
string doubletostr(double val)
{
	char buffer[100];
	string str;
	sprintf(buffer, "%f", val);
	str.assign(buffer);
	return str;
}

// Multiply two values
string multiply(string str1, string str2)
{
	double val = strtodouble(str1) * strtodouble(str2);
	return doubletostr(val);
}

// Divide two values
string divide(string str1, string str2)
{
	double val = strtodouble(str2) / strtodouble(str1);
	return doubletostr(val);
}

// Add two values
string add(string str1, string str2)
{
	double val = strtodouble(str1) + strtodouble(str2);
	return doubletostr(val);
}

// Subtract two values
string subtract(string str1, string str2)
{
	double val = strtodouble(str2) - strtodouble(str1);
	return doubletostr(val);
}

// Perform an operation with an exponent
string power(string str1, string str2)
{
	double val = pow(strtodouble(str2), strtodouble(str1));
	return doubletostr(val);
}

// Pop items off the stack, solve, and re-add to the stack.  This is the process
// for solving postfix format
string solveRPN(string str)
{
	stack<string> rpn;
	string tempStr, str1, str2;
	for(int i = 0; i <= str.length(); i++)
	{
		switch(str[i])
		{
			case '^': 
				str1 = rpn.top(); 
				rpn.pop(); 
				str2 = rpn.top(); 
				rpn.pop(); 
				rpn.push(power(str1, str2));
				break;
			case '*': 
				str1 = rpn.top(); 
				rpn.pop(); 
				str2 = rpn.top(); 
				rpn.pop(); 
				rpn.push(multiply(str1, str2));
				break;
			case '/': 
				str1 = rpn.top(); 
				rpn.pop(); 
				str2 = rpn.top(); 
				rpn.pop(); 
				rpn.push(divide(str1, str2));
				break;
			case '+': 
				str1 = rpn.top(); 
				rpn.pop(); 
				str2 = rpn.top(); 
				rpn.pop(); 
				rpn.push(add(str1, str2));
				break;
			case '-': 
				str1 = rpn.top(); 
				rpn.pop(); 
				str2 = rpn.top(); 
				rpn.pop(); 
				rpn.push(subtract(str1, str2));
				break;
			case ' ': if(tempStr != "") { rpn.push(tempStr); } tempStr = ""; break;
			default: tempStr.push_back(str[i]); break;
		}
	}
	return rpn.top();
}

// Check to see if the first operator has a higher rank than the second
// operator.  This must been done because when solving the formula we must
// follow the rules of order of operations.  PEMDAS
bool opGreaterEqual(char a, char b)
{
	bool stat = false;
	int n, m;
	if(a == '^') { n = 3; }
	if(b == '^') { m = 3; }
	if(a == '*' || a == '/') { n = 2; }
	if(b == '*' || b == '/') { m = 2; }
	if(a == '+' || a == '-') { n = 1; }
	if(b == '+' || b == '-') { m = 1; }
	if(n >= m) { stat = true; }
	return stat;
}

// Infix notation is the general way we write an equation.  For example infix notation
// is 5+3*4.  Converting to postfix notation or reverse polish notation makes use of stacks
// which makes it very easy told solve the formula.
string infixToPostfix(string s)
{
	int len = s.length();
	string rpn = "";
	stack<char> operand;
	for(int i = 0; i < len; i++)
	{
		if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '^')
		{
			while(!operand.empty() && operand.top() != '(')
			{
				if(opGreaterEqual(operand.top(), s[i]))
				{
					rpn += operand.top();
					operand.pop();
				}
				else 
				{
					break;
				}
			}
			operand.push(s[i]);
		}
		else if(s[i]=='(')
		{
			operand.push('(');
		}
		else if(s[i]==')')
		{
			while(!operand.empty() && operand.top() != '(')
			{
				rpn += operand.top();
				operand.pop();
			}
			if(!operand.empty()) 
			{
				operand.pop();
			}
		}
		else if(s[i] >= '0' && s[i] <= '9')
		{
			rpn += s[i];
			if(i < len)
			{
				if(s[i+1] < '0' || s[i+1] > '9')
				{
					rpn += ' ';
				}
			}
		}
	}
	while(!operand.empty())
	{
		rpn += operand.top();
		operand.pop();
	}
	return rpn;
}

int main()
{
	string input;
	cout << "> ";
	getline(cin, input);
	input = trimspaces(input);
	cout << "IFN: " << input << endl;
	input =  infixToPostfix(input);
	cout << "RPN: " << input << endl;
	cout << "Solved: " << solveRPN(input) << endl;
	return 0;
}