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

Show what you have tried and what problems you encountered. SO is mainly for giving help with specific problems. As written now you are asking for someone else to write the code for you. — super

Tracer Tracer · Accepted Answer · 2019-12-22T18:19:18

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.

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

2 Answers