[FIXED] Recursive generator of random algebraic expressions tree issue

Issue

Problem description

I am trying to write a math test for my little son. Such test must generate a list of random algebraic expressions according to certain rules and check the correctness of solution.

In particular, I want to generate expressions consisting strictly of a given number of operators that are selected from a certain list. For example generate a list of expression consisting of 3 operators of addition and subtraction in random order like:

• 12 - (5 + 2) + 2
• 3 + 4 - 2 + 10
• and so on

To represent and calculate the expression, I use the binary expression tree structure. Each tree consists of either a Leaf or a Node that contains an Operator and two subtrees. This is a simple recursive structure and I want to work with it only recursively. No setters in the classes of the tree. I can only use constructors to create a tree.

Leaf class

public final class Leaf implements Expression {

    private final int value;
    
    public Leaf(int value) {
        this.value = value;
    }
    
    // ...
}

Node Class

public final class Node implements Expression {

    private final Operator operator;
    private final Expression left;
    private final Expression right;
    
    public Node(@NotNull Operator operator, 
                @NotNull Expression left,
                @NotNull Expression right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }
    
    // ...
}

And Operator is a simple Enum type. I simplify my classes for the purposes of this question.

My issue

I am trying to build an expression based on the following rules:

• There should be at least one operator in the expression, so my tree always starts from the Node.
• I choose a random operator from a given list and increase the number of operators used
• While this number less than the given number of operators I construct the left and rights subtree for current Node.
• The left subtree can be randomly either a Leaf or Node
• The right subtree can also be either a Leaf or Node, but if the left subtree is a Leaf and there are still unused operators, then the right must be a Node.

I wrote such an expression builder:

public class SmartExpressionBuilder {

    private final Random random = ThreadLocalRandom.current();
    private final List<Operator> allowedOperators;
    private final int numberOfOperators;

    public SmartExpressionBuilder(List<Operator> allowedOperators, int numberOfOperators) {
        this.allowedOperators = allowedOperators;
        this.numberOfOperators = numberOfOperators;
    }

    private int operatorsUsed;

    public Expression build() {
        operatorsUsed = 0;
        return helper();
    }

    private Expression helper() {
        if (operatorsUsed == numberOfOperators) return randomLeaf();

        Operator op = randomOperator();

        Expression left = random.nextBoolean() ? helper() : randomLeaf();
        Expression right = (left instanceof Leaf || random.nextBoolean()) ? helper() : randomLeaf();

        return new Node(op, left, right);
    }

    private Operator randomOperator() {
        operatorsUsed++;
        return allowedOperators.get(random.nextInt(allowedOperators.size()));
    }

    private Leaf randomLeaf() {
        return new Leaf(random.nextInt(1, 10));
    }

    public static void main(String[] args) {
        final var builder = new SmartExpressionBuilder(List.of(Operator.ADD, Operator.SUB), 4);
        IntStream.range(0, 10)
                .mapToObj(ignored -> builder.build())
                .forEach(exp -> {
                    System.out.printf("%s = %d%n", exp.infix(), exp.evaluate());
                    TreePrinter.print(exp);
                });
    }
}

This works in principle. In the sense that a tree really builds with a given number of operators. But there's a problem. I get nodes looks like this:

    Node                Node
   /    \      or      /    \
 Leaf  Node          Node  Leaf

For example my actual expression and tree may looks like this:

4 + 4 - (1 + 3) - 2 = 2
            +
    4               -
                -       2
              4   +        
                 1 3        

but i never get tree like this:

    Node                  +
   /    \        or    -     +
 Node  Node           5 2  2   -
                              6 1

I understand what the essence of the problem is. In my recursive function, I always go into the left tree first. And every time my random generates an the Node is in the left subtree, and not the Leaf, recursion dive deeper and deeper int the left subtree until unused operators ends. This means that if an Node appeared in the left subtree, then Node cannot appear in the right at the same depths of tree.

I broke my brain, but did not figure out how to solve this problem without abandoning the recursive construction of my tree.

I would be very grateful for any ideas how build nodes of this kind

    Node
   /    \
 Node  Node

Solution

It's going to be very difficult to get balanced trees this way - you have to tune it very carefully for the left tree to probably give you half the operators. I don't think it's worth it.

Instead, I would pick the target number of operators at the top level - that would be a minimum plus some random range to generate larger or smaller expressions - and then randomly assign some of them to each subtree. So you have a recursive call that takes a size parameter; if size==0, generate a leaf, otherwise make a node, and split size-1 into a leftSize and rightSize to pass to the recursive calls.

Here's some rough pseudocode (I don't write much Java these days, but hopefully it makes the algorithm clear)

private Expression build(int size){
  if (size == 0) return buildLeaf()
  else {
    leftSize = randomInt(size-1)
    rightSize = size - 1 - leftSize
    leftTree = build(leftSize)
    rightTree = build(rightSize)
    return buildNode(leftTree, rightTree, getRandomOperator())
   }
}

Does that make sense and work for you?

Answered By - Edward Peters
Answer Checked By - Mildred Charles (JavaFixing Admin)