Need help generating random expression tree with limited depth in C++

Question

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:

• Each node has zero, one or two children.
• Only nodes containing operators can have children.
• All leaf nodes must be operands.

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

Answer 1

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:

1. depth: 2 => B * A
2. depth: 4 => ((B - A) * A) * (A * C)
3. depth: 5 => (((C - C) - A) + (B + B)) * C
4. depth: 1 => C
5. depth: 1 => A

I hope this can be of use to someone, or please let me know if something needs fixing.

Answer 2

Just shoving in random stuff in the tree will not work. There is a finite chance that you start with 2 to the power maxDepth operators, so there is no more room for operands.

What you want to do is start at a node, then if it's at maxDepth, always choose an operand, otherwise choose an operator or operand at random. If you chose an operator, then repeat this recursively for the left and right children.

If the depth of the tree has to be exactly maxDepth, then you will need to modify this algorithm a bit more.