I have found this example: Insert nodes in expression trees and have made some minor modifications:
class Node {
public:
std::string data;
Node* left, * right;
Node* parent; // operator
Node(std::string d, Node* p) : data(d), left(NULL), right(NULL), parent(p) {}
};
class ExpressionTree {
public:
Node* root;
int tsize;
ExpressionTree() : root(NULL), tsize(0) {}
void insert(string s);
bool isOperator(string value);
};
bool ExpressionTree::isOperator(string value) {
if (value == "+" || value == "-" ||
value == "*" || value == "/" ||
value == "==")
return true;
return false;
}
void ExpressionTree::insert(std::string s) {
if (root == NULL) {
root = new Node(s, NULL);
++tsize;
}
else {
Node* current = root;
while (true) {
if (isOperator(current->data)) {
if (current->left == NULL) {
current->left = new Node(s, current);
++tsize;
return;
}
else if (current->right == NULL) {
current->right = new Node(s, current);
//++tsize;
return;
}
else {
if (isOperator(current->left->data)) {
current = current->left;
continue;
}
else if (isOperator(current->right->data)) {
current = current->right;
continue;
}
else {
if (current->parent) {
current = current->parent->right;
continue;
}
else {
//std::cout << "Error: only nodes who hold operators "
// << "can have children." << std::endl;
return;
}
}
}
}
else {
//std::cout << "Error: only nodes who hold operators "
// << "can have children." << std::endl;
return;
}
}
}
}
void inorder(Node* node) {
if (node) {
if (node->left && node->parent)
cout << "(";
inorder(node->left);
cout << node->data;
inorder(node->right);
if (node->right && node->parent)
cout << ")";
}
}
What I need is to create random expression tree with limited depth based on input vectors
int maxDepth = 2;
vector<string> operands = { "A", "B", "C" };
vector<string> operators = { "+", "*", "-" };
It would be great if something like this could be implemented:
ExpressionTree expression = generateRandomTree(operands, operators, maxDepth);
Possible inorder solutions in this case are A, B, C (tree depth = 1) or A + B, A - A, C - A etc. if tree depth > 1.
As in the previous link, to make a valid expression a following rules must be applied:
Method insert does a good job, but I simply don't know how to generate a random expression tree based on this code.. I appreciate your help in resolving this problem.
Edit: Think out loud, I should probably just repeat executing insert with random operand or random operator (50-50% chance) until all leaf nodes become operands or maximum depth is reached. Also, I would need to force only random operands for the maxDepth tree level (if it is reached). Still, implementation is the problem I have..
I think I did it... At least the results seem to be good.
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
using namespace std;
class Node {
public:
string data;
string type;
Node* left, * right;
Node* parent; // operator
Node(string d, string t) : data(d), type(t), left(NULL), right(NULL), parent(NULL) {}
};
class ExpressionTree {
public:
Node* root;
int tsize;
ExpressionTree() : root(NULL), tsize(0) {}
//void insert(string s);
void addLeafNode(Node* node);
bool isOperator(string value);
};
bool ExpressionTree::isOperator(string value) {
if (value == "+" || value == "-" ||
value == "*" || value == "/" ||
value == "==")
return true;
return false;
}
void inorder(Node* node) {
if (node) {
if (node->left && node->parent)
cout << "(";
inorder(node->left);
cout << node->data;
inorder(node->right);
if (node->right && node->parent)
cout << ")";
}
}
void randomOperandOrOperator(vector<string> operands, vector<string> operators, string* value, string* type, bool maxDepth) {
if (!operators.size())
maxDepth = 1;
if (maxDepth == 1) {
*value = operands[rand() % operands.size()];
*type = "operand";
}
else {
int percentage = rand() % 100 + 1;
if (percentage <= 50) {
*value = operands[rand() % operands.size()];
*type = "operand";
}
else {
*value = operators[rand() % operators.size()];
*type = "operator";
}
}
}
Node* getFirstFreeOperatorLeafNode(Node* root) {
Node* res = NULL;
if (root == NULL)
return NULL;
if (root->type == "operator") {
if (root->left == NULL || root->right == NULL)
return root;
if(root->left != NULL)
res = getFirstFreeOperatorLeafNode(root->left);
if (res == NULL && root->right != NULL)
res = getFirstFreeOperatorLeafNode(root->right);
}
return res;
}
void ExpressionTree::addLeafNode(Node* node) {
// tree is empty?
if (root == NULL) {
root = node;
node->parent = NULL;
node->left = NULL;
node->right = NULL;
}
else {
// add new node to first free operator leaf node
Node* lastOperatorLeaf = getFirstFreeOperatorLeafNode(root);
if (lastOperatorLeaf != NULL) {
if (lastOperatorLeaf->left == NULL) {
lastOperatorLeaf->left = node;
node->parent = lastOperatorLeaf->left;
}
else
if (lastOperatorLeaf->right == NULL) {
lastOperatorLeaf->right = node;
node->parent = lastOperatorLeaf->right;
}
}
}
}
int getDepth(Node* node){
if (node == NULL)
return 0;
else{
int lDepth = getDepth(node->left);
int rDepth = getDepth(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
int main() {
srand(time(NULL));
vector<string> operands = { "A", "B", "C" };
vector<string> operators = { "+", "*", "-" };
int maxDepth = 5;
for (int i = 0; i < 5; i++) {
ExpressionTree expression;
do {
string value, type;
randomOperandOrOperator(operands, operators, &value, &type, (getDepth(expression.root) + 1 >= maxDepth));
expression.addLeafNode(new Node(value, type));
} while (getFirstFreeOperatorLeafNode(expression.root) != NULL);
cout << i + 1 << ". depth: " << getDepth(expression.root) << " => ";
inorder(expression.root);
cout << endl;
}
return 0;
}
5 samples for maxDepth = 5:
- depth: 2 => B * A
- depth: 4 => ((B - A) * A) * (A * C)
- depth: 5 => (((C - C) - A) + (B + B)) * C
- depth: 1 => C
- depth: 1 => A
I hope this can be of use to someone, or please let me know if something needs fixing.