//*****************************************************************************
// Postfix expression evaluation
// 11/13/2012
// by DJH
//
// all applicable copyrights apply
//
// this program evaluates an input postfix string
// 
//
// created using Dev-C++ 5.2.0.3
//*****************************************************************************

// ----------------------------------libraries---------------------------------

#include <iostream>    			// For cin, cout and endl
#include <string>
#include <cctype>
#include <vector>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <iomanip>

using namespace std;
// ------------------------------ Globals -------------------------------------
string postfix;

// --------------------------- stack class ------------------------------------
class Stack{
public:
  enum {MaxStack = 50};
  void init() {top = -1;}
  void push( double p ){
    if ( isFull() ) {
      cerr << "Full Stack. DON'T PUSH\n";
      return;
    }
    else {
      arr[ ++top ] = p;
      cout << "Just pushed " << p << endl;
      return;}
  }
  int pop() {
    if (isEmpty() ) {
      cerr << "\tEmpty Stack. Don't Pop\n\n";
      return 1;
    }
    else 
      return arr[top--];
  }
  bool isEmpty() {return top < 0 ? 1 : 0;}
  bool isFull() {return top >= MaxStack -1 ? top : 0;}
  void dump_stack() {
    cout << "The Stack contents, from top to bottom, from a stack dump are: " << endl;
    for (int s = top; s >= 0; s--)
      cout << "\t\t" << arr[s] << endl;
  }
private:  
  int top;
  double arr[MaxStack];
}pStack;
// ------------------------------ end stack class -----------------------------

// -----------------------------function prototypes----------------------------
void evalPostfix (string);
double decimalEvaluate (string, int, double);
// ----------------------------------------------------------------------------

// -----------------------------------Main()-----------------------------------
int main()
{
	cout << "Enter a postfix expression\n\t (without spaces - using '_' for delimiters):\n\t";
	cout << "For example: 8_5_3_+_*_2_/_5_+\n" << endl;
	getline(cin, postfix);

//	postfix = "7_2_*_5_+_2_*";
	cout << "You entered: " << postfix << endl;
	
int c=0;

while ( postfix[c] !='\0' )
	{
	++c;			// this loop counts the characters in the input string including whitespace
	}

cout <<	"\tThe string length is:\t" << c << endl;
evalPostfix (postfix);
int result = pStack.pop();
cout << "The result of the postfix expression is: " << result << endl;

	
/*
stack commands:
	Stack a_stack; 			// creates new stack
	a_stack.init();			// initializes top element
	a_stack.pop(); 			// pops top of stack
	a_stack.push(n); 		// push element to top of stack
	a_stack.dump_stack(); 	// displays the contents of the stack from top to bottom
*/	
	return 0;
	cin.get();
}



// --------------------------------end of Main()-------------------------------


// ------------------------------functions follow------------------------------
void evalPostfix (string)
{
	double ch=0,dc=0,b=0,a=0,d=0;
	double tempDC=0;
	double tempDCD=0;
	char op;
	int i=0,j=0,k=0,m=0,n=0,q=0;
	while (postfix[i] != '\0')
	{

	if (postfix[i] == '_') {i++;}
	
	else if (isdigit (postfix[i]))
			{
				ch = postfix[i] - '0'; // for numbers only
				j=i+1;
				while (postfix[j] != '_')
				{
					if (isdigit (postfix[j]))
					{
					ch = ch*10 + (postfix[j] - '0');
					k=j+1;
					 if (postfix[k] == '.') // this accounts for decimals by skipping the '.' and conducting operations on trailing numbers
						{
						dc=0;
						decimalEvaluate (postfix, k, dc);
						dc = tempDC / tempDCD;
						d=ch+dc;
						k++;
						
						}
					j=k-1;
					j++;					
					}
				}
cout << "Post decimal function k: " << k << endl;
cout << "Post decimal function dc: " << setprecision (12) << dc << endl;
cout << "Post decimal function d: " << d << endl;
				pStack.push(d);
				i=j-1;
				i++;
			}
	else if (postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/' || postfix[i] == '^')
			{  
			b=pStack.pop();
			a=pStack.pop();
			op = postfix[i]; // for operators only
			switch(op)
				{
				case '+':pStack.push(a+b);
					break;
				case '-':pStack.push(a-b);
					break;
				case '*':pStack.push(a*b);
					break;
				case '^':pStack.push(pow(a,b));
					break;
				case '/':if(b==0)
					 {
						 cout << "Division by zero not allowed!" << endl;
						 cin.get();
						 exit(0);
					 }
					 pStack.push(a/b);
				default:cout << "Invalid Operation" << endl;
				}
			i++;
			}
	
	}
}
// ----------------------------------------------------------------------------

double decimalEvaluate (string postfix, int k, double dc)
{
	dc=0;
	double tempDC=0;
	double tempDCD=0;
	
	int n=0, m=0,lenDC=0;
	
	n=k;

while ( postfix[n] != '_' )
	{
	if ((isdigit (postfix[n]))== false)
		{
		n++;
		}
cout << "This step (1) n: " << n << endl;		
	if (isdigit (postfix[n]))
		{
		m=n;
		while ( postfix[m] != '_' ) // assumes characters between a '.' and '_' are all digits (may need to check)
			{
			lenDC++;
			m++;			// this loop counts the digits in the input trailing a decimal point
			}
cout << "This step (2) m: " << m << endl;
cout << "This step (2) lenDC: " << lenDC << endl;								
		while ((postfix[n]) != '_')
			{
			tempDC = tempDC*10 + (postfix[n]) - '0';
			n++;
			}
cout << "This step (3) n: " << n << endl;
cout << "This step (3) tempDC: " << tempDC << endl;
		}
	k=n;
	
	tempDCD = pow(10,lenDC);
	
	dc = tempDC / tempDCD;

cout << "This step (4) k: " << k << endl;
cout << "This step (4) tempDCD: " << tempDCD << endl;
cout << "This step (4) tempDC: " << tempDC << endl;
cout << "This step (4) dc: " << dc << endl;
	}
	return dc,k,tempDC,tempDCD;
}