#include <iostream>
#include <string>
#include <stack>
#include <sstream>
#include <stdlib.h>

using namespace std;

template <class elemType>
struct binaryTreeNode
{
	elemType info;
	binaryTreeNode<elemType>* llink;
	binaryTreeNode<elemType>* rlink;
};

template <class elemType>
class binaryTreeType
{
protected:
	binaryTreeNode<elemType> *root;

public:
	bool isEmpty() const;
	void insert(const elemType& insertNode);
	void inorderTraversal() const;
	void postorderTraversal() const;
	binaryTreeType();


private:
	void inorder(binaryTreeNode<elemType> *p) const;
	void postorder(binaryTreeNode<elemType> *p) const;
};

template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
	root = NULL;
}

template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const {
	return (root == NULL);
}

template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
	inorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
	postorder(root);
}

template <class elemType>
void binaryTreeType<elemType>::inorder(binaryTreeNode<elemType> *p) const
{
	if(p !=NULL)
	{
		inorder(p->llink);
		cout<< p->info << " ";
		inorder(p->rlink);
	}
}

template <class elemType>
void binaryTreeType<elemType>::postorder(binaryTreeNode<elemType> *p) const
{
	if(p !=NULL)
	{
		postorder(p->llink);
		postorder(p->rlink);
		cout<< p->info << " ";
	}
}

class mathProcessor : public binaryTreeType<string> {
public:
	mathProcessor();
	void displayStatus();
	void processExpression(string &expression);
	double compute();

private:
	stack<string> theStack;
	double convertStringToDouble(string const &s);
	string convertDoubleToString(const double d);
	void reset();

	bool isDigit(char c);
	bool isOperator(char c);
	void processExpression(binaryTreeNode<string>* p);
	void compute(binaryTreeNode<string> *p);

protected:
	string expression;
	int position;
};

void mathProcessor :: reset() {
	expression = "";
	position = 0;
	theStack.empty();
}

double mathProcessor::convertStringToDouble(string const &s) {
	istringstream iss(s);
	double x;
	iss >> x;
	return x;
}

string mathProcessor::convertDoubleToString(const double d) {
	ostringstream oss;
	oss << d;
	return oss.str();
}

mathProcessor::mathProcessor() {
	reset();
}

bool mathProcessor::isDigit(char c) {
	return (c == 48 || c == 49 || c == 50 || c == 51 || c == 52 || c == 53 || c == 54 || c == 55 ||  c == 56 ||  c == 57);
}

bool mathProcessor::isOperator(char c) {
	return (c == '+' || c == '-' || c == '*' || c == '/');
}

void mathProcessor::processExpression(string& expression) {
	if(expression == ""){
		return;
	}
	else {
		reset();
		this->expression = expression;
		binaryTreeNode<string>* newNode;
		newNode = new binaryTreeNode<string>;
		root = newNode;
		processExpression(root);
	}
}

void mathProcessor::processExpression(binaryTreeNode<string>* p){
	 do{
		if(expression[position] == '('){
			binaryTreeNode<string> *newNode;
			newNode = new binaryTreeNode<string>;
			p->llink = newNode;
			newNode->llink = NULL;
			newNode->rlink = NULL;
			position++;
			processExpression(newNode);
		}
		else if (isDigit(expression[position])){
			string temp = " ";
			while(isDigit(expression[position])){
				temp += expression[position];
				position++;
			}
			p->info = temp;
			return;
		}
		else if(isOperator(expression[position])){
			p->info = expression[position];
			binaryTreeNode<string> *rightNode;
			rightNode = new binaryTreeNode<string>;
			p->rlink = rightNode;
			rightNode->llink = NULL;
			rightNode->rlink = NULL;
			position++;
			processExpression(rightNode);
		}
		else if(expression[position] == ')'){
			return;
		}
	 }while(position < expression.size());
}

//double mathProcessor::compute() {
//	compute(root);
//
//	return;
//}

void mathProcessor::compute(binaryTreeNode<string> *p) {

}

void mathProcessor::displayStatus() {
	cout<< "The data in an in-order traversal is: ";
	inorderTraversal();
	cout<<endl;
	cout<< "The data in a post-order traversal is: ";
	postorderTraversal();
	cout<<endl;
}

int main() {

	mathProcessor *mp = new mathProcessor;
	string expression = "(2+3)";
	mp->processExpression(expression);
	mp->displayStatus();
	//cout <<  "The result is: " << mp->compute() << endl;
	expression = "(123+456)";
	mp->processExpression(expression);
	mp->displayStatus();
	//cout <<  "The result is: " << mp->compute() << endl;
	expression = "(8-5)";
	mp->processExpression(expression);
	mp->displayStatus();
	//cout <<  "The result is: " << mp->compute() << endl;
	expression = "((3-4)-5)";
	mp->processExpression(expression);
	mp->displayStatus();
	//cout <<  "The result is: " << mp->compute() << endl;
	/*expression = "(3*(8/2))";
	mp->processExpression(expression);
	mp->displayStatus();*/
	//cout <<  "The result is: " << mp->compute() << endl;
	/*expression = "((((3+12)-7)*120)/(2+3))";
	mp->processExpression(expression);
	mp->displayStatus();*/
	//cout <<  "The result is: " << mp->compute() << endl;
	/*expression = "(((((9+(2*(110-(20/2))))*8)+1000)/2)-((400*2500)-1000001)";
	mp->processExpression(expression);
	mp->displayStatus();*/
	//cout <<  "The result is: " << mp->compute() << endl;*/

	system("pause");
	return 0;
}