I'm trying to evaluate an expression using a binary tree. The tree has this characteristics:
- Each node has zero, one or two children.
- Only nodes containing operators can have children.
- All leaf nodes must be numbers.
- For the sake of simplicity, the only operators allowed are
*
and+
Something like those ones:
This is my tree class:
class ExpressionTree {
struct Node {
std::string data;
Node *leftChild, *rightChild;
Node(std::string d): data(d), leftChild(NULL), rightChild(NULL) {}
} *root;
uint tsize;
public:
ExpressionTree(): root(NULL), tsize(0) {}
Node* treeRoot() { return root; }
void insert(std::string s);
};
And this is my insert function:
void insert(std::string s) {
if (root == NULL) {
root = new Node(s);
++tsize;
} else {
Node* current = root;
while (true) {
if (is_operator(current->data)) {
if (current->leftChild == NULL) {
current->leftChild = new Node(s);
++tsize;
return;
} else if (current->rightChild == NULL) {
current->rightChild = new Node(s);
++tsize;
return;
} else {
if (is_operator(current->leftChild->data)) {
current = current->leftChild;
continue;
} else if (is_operator(current->rightChild->data)) {
current = current->rightChild;
continue;
} else {
std::cout << "Error: only nodes who hold operators"
<< " can have children." << std::endl;
return;
}
}
}
}
}
}
The problem is in this function. I wrote it starting from a function to insert nodes in a Binary Search tree, but it doesn't work. When I run a simple main (that, using insert()
, adds the nodes of the second tree one at time) it crashes without returning any error, only a windows 7 dialog who asks to check for an online solution.
I think that the main problem is that it does not inspect all the elements of a tree, but only a branch, and for this reason it appends new nodes in an illegal way. Unfortunately, I can't figure out how to solve this.
I hope that this question is not too much specific.
Note: is_operator()
takes a string, and return true
if it's +
or *
, and false otherwise.