1. ## 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;

}
}```

2. 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