Please Excuse My Dear Aunt Sally (Expression Tree Help)

I am trying to make a calculator but since I am doing this on my own spare time, in the summer, I have no where to turn to but here for help.

I know the order in which the data must be inserted into the tree but I am stuck in implementing a function that does it. So far I am thinking that the constructor of the ExpressionTree accepts the Equation and the Root node's Node->Insert function is called and recursively puts stuff into the tree's branches.

So far I only have this. It is just a short test of what I have so far that adds 5 + 3 and outputs 8 to let you all know what I am sort of going for.

Can you offer me any suggestions. Thank you for your time.

Main.cpp

Code:

#include <iostream>

#include "ExpressionTree.hpp"

int main()
{
	ExpresionTree Tree("");
	
	Tree.Root = new Node();
	Tree.Root->type = 1;
	Tree.Root->Data = "+";
	
	Tree.Root->Left = new Node();
	Tree.Root->Right = new Node();
	
	Tree.Root->Left->type  = 0;
	Tree.Root->Right->type  = 0;
	
	Tree.Root->Left->Data  = "5";
	Tree.Root->Right->Data  = "3";	
	
	std::cout << Tree.Value();
	

	std::cin.get();
	return 0;
}

StringFunctions.hpp

Code:

#ifndef STRING_FUNCTIONS_H
#define STRING_FUNCTIONS_H

#include <sstream>
#include <cmath>

std::string DoubleToString(double num);
double StringToDouble(std::string str);

#endif

StringFunctions.cpp

Code:

#include "StringFunctions.hpp"

double StringToDouble(std::string str)
{
	double num;
	std::istringstream is(str);
	is >> num;
	return num;
}

std::string DoubleToString(double num)
{
	std::stringstream strm;
	strm << num;
	return strm.str();
}

ExpressionTree.hpp

Code:

#ifndef EXPRESSION_TREE_H
#define EXPRESSION_TREE_H

#include <iostream>
#include <cmath>

#include "StringFunctions.hpp"

#define TYPE_NUMBER		0
#define TYPE_OPERATOR	1
#define TYPE_FUNCTION 	2

class Node
{
public:
	Node();
    Node(std::string Expression);
    int type;
    Node *Left;
    Node *Right;
    Node *Middle;
    std::string Data;
    int Insert(std::string Expression);
};

class ExpresionTree
{
public:
    ExpresionTree(std::string Expression);
	~ExpresionTree();
	
	std::string Value();
	std::string GetValue(Node* n);

    void Clear(Node *n);
	Node *Root;
};

#endif

ExpressionTree.cpp

Code:

#include "ExpressionTree.hpp"

Node::Node() {}

Node::Node(std::string Expression)
{
	this->Insert(Expression);
}

int Node::Insert(std::string Expression)
{
    

}

ExpresionTree::ExpresionTree(std::string Expression)
{


}

ExpresionTree::~ExpresionTree()
{
	Clear(Root);
}

void ExpresionTree::Clear(Node *n)
{
    if(n)
    {
        Clear(n->Left);
        Clear(n->Right);
        Clear(n->Middle);
        delete n;
    }
}
std::string ExpresionTree::Value()
{
	return ExpresionTree::GetValue(Root);
}

std::string ExpresionTree::GetValue(Node *n)
{
	if (n->type == TYPE_NUMBER)
	{
		return n->Data;
	}
	else if (n->type == TYPE_FUNCTION)
	{
		double middlevalue = StringToDouble(GetValue(n->Middle));
		std::string finalvalue;
		
		if (n->Data == "()")
		{
			finalvalue = DoubleToString((middlevalue));
		}		
		else if (n->Data == "cos")
		{
			finalvalue = DoubleToString(cos(middlevalue));
		}
		else if (n->Data == "sin")
		{
			finalvalue = DoubleToString(sin(middlevalue));
		}
		else if (n->Data == "tan")
		{
			finalvalue = DoubleToString(tan(middlevalue));
		}
		else if (n->Data == "sqrt")
		{
			finalvalue = DoubleToString(sqrt(middlevalue));
		}
		else if (n->Data == "abs")
		{
			finalvalue = DoubleToString(fabs(middlevalue));
		}
	}
	else if (n->type == TYPE_OPERATOR)
	{
		double leftvalue = StringToDouble(GetValue(n->Left));
		double rightvalue = StringToDouble(GetValue(n->Right));
		std::string finalvalue;

		if (n->Data == "+")
		{
			finalvalue = DoubleToString(leftvalue + rightvalue);
		}
		else if (n->Data == "-")
		{
			finalvalue = DoubleToString(leftvalue - rightvalue);
		}
		else if (n->Data == "*")
		{
			finalvalue = DoubleToString(leftvalue * rightvalue);
		}
		else if (n->Data == "/")
		{
			finalvalue = DoubleToString(leftvalue / rightvalue);
		}
		else if (n->Data == "MOD")
		{
			finalvalue = DoubleToString(int(leftvalue) % int(rightvalue));
		}
		else if (n->Data == "^")
		{
			finalvalue = DoubleToString(pow(leftvalue, rightvalue));
		}
		return finalvalue;

	}
}

I recommend you first write a context free grammar for the expressions you want to accept. After you have your grammar, you can usually turn it into a recursive descent parser fairly easily.

Example 2 will cover quite a bit of your grammar.

http://en.wikipedia.org/wiki/Context-free_grammar

You may also want to read

http://en.wikipedia.org/wiki/Recursive_descent_parser