Я нашел этот пример: Вставка узлов в деревья выражений и внесла несколько небольших изменений:
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.
Как и в предыдущей ссылке, для создания допустимого выражения должны применяться следующие правила:
- Каждый узел имеет ноль, одного или двух дочерних элементов.
- Только узлы, содержащие операторы, могут иметь дочерние элементы.
- Все конечные узлы должны быть операндами.
Метод insert хорошо работает, но я просто нене знаю, как сгенерировать дерево случайных выражений на основе этого кода. Я ценю вашу помощь в решении этой проблемы.
Редактировать: Подумайте вслух, вероятно, мне следует просто повторить выполнение insert со случайным операндом или случайным оператором (вероятность 50-50%), пока все листовые узлы не станут операндами или не будет достигнута максимальная глубина. Кроме того, для уровня дерева maxDepth (если он достигнут) мне понадобятся только случайные операнды. Тем не менее, реализация - это проблема, с которой я столкнулся ..