需要帮助在 C++ 中生成深度有限的随机表达式树

Question

我找到了这个例子： Insert nodes in expression trees 并做了一些小修改：

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 << ")";
    }
}

我需要的是基于输入向量创建具有有限深度的随机表达式树

int maxDepth = 2;
vector<string> operands = { "A", "B", "C" };
vector<string> operators = { "+", "*", "-" };

如果能实现这样的东西就好了：

ExpressionTree expression = generateRandomTree(operands, operators, maxDepth);

在这种情况下可能的中序解决方案是 A、B、C（树深度 = 1）或 A + B、A - A、C - A 等。如果树深度 > 1。

与前面的 link 一样，要使表达式有效，必须应用以下规则：

每个节点有零个、一个或两个children。
只有包含运算符的节点才能有 children.
所有叶节点都必须是操作数。

方法insert做得很好，但我就是不知道如何根据这段代码生成随机表达式树。感谢你帮助解决了这个问题。

编辑： 大声思考，我可能应该用随机操作数或随机运算符（50-50% 的机会）重复执行 insert，直到所有叶节点都变成达到操作数或最大深度。另外，我只需要为 maxDepth 树级别（如果达到）强制随机操作数。仍然，实施是我遇到的问题..

Answer 1

只是把随机的东西塞进树里是行不通的。您从 2 的 maxDepth 次幂运算符开始的机会有限，因此没有更多的操作数空间。

你要做的是从一个节点开始，如果它在 maxDepth，总是选择一个操作数，否则随机选择一个运算符或操作数。如果您选择了一个运算符，则对左右 children.

递归重复此操作

如果树的深度必须恰好是maxDepth，那么您需要稍微修改一下这个算法。

Answer 2

我觉得我做到了...至少结果看起来不错

#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;
}

maxDepth = 5 的 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

我希望这对某人有用，或者如果需要修复请告诉我。

需要帮助在 C++ 中生成深度有限的随机表达式树

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

c++

algorithm

expression-trees