11 Replies Latest reply on Dec 16, 2008 6:43 PM by 807589

Creating random expression trees

(operator at the node, operands at the 2 branches)

I need an algorithm or at least a point in the right direction in how to create random expression trees with X number of characters (characters being either numbers or operators). I'm been taking stabs at this for a few days without luck. I'd appreciate any help.
• 1. Re: Creating random expression trees
with X number of characters (characters being either numbers or operators)
huh? example?
is "12.3 + 4" equal to 3 (number is one character), 5 (each number), 6 (decimal point) or 8 (whitespace) characters?

are you familiar with recursion?
• 2. Re: Creating random expression trees
i'm using "characters" as a euphemism. call them tokens, whatever. "12.3 + 4" ===> + at node root, 12.3 and 4 at left and right branches respectively.

and yes i'm quite familiar with recursion. i've simply been unable to come up with an algorithm that allows for the creation of completely random expression trees.
• 3. Re: Creating random expression trees
i'm quite familiar with recursion. i've simply been unable to come up with an algorithm that allows for the creation of completely random expression trees.
So what have you tried? ... I mean generating random anything in java isn't hard. Is it?

Cheers. Keith.
• 4. Re: Creating random expression trees
dftp84 wrote:
and yes i'm quite familiar with recursion. i've simply been unable to come up with an algorithm that allows for the creation of completely random expression trees.
``````recurse(tree){

if(left is null){ random operator or operand, return }
if(right is null){ random operator or operand, return }
if(parent != null){ recurse(parent), return }
finished()

}``````
One way to guarantee randomness would be to create every tree possible for a given size,
pick a random tree and then fill in the operator and operand values.
• 5. Re: Creating random expression trees
(Okay: size = # of tokens in the tree)

Hint: you can have a tree of size 1 (ex: 17) and you can have a tree of size 3 (ex: 42 + 17) but you can't have a tree of size 2!

So: to generate a tree of size 10, the first step is to split 10 into lsize & rsize (where 10 = lsize + rsize + 1):

1 & 8
3 & 6
4 & 5
5 & 4
6 & 3
8 & 1

Now rite dat codez!
• 6. Re: Creating random expression trees
Now rite dat codez!
yea, i know id love to see a binary tree with 10 nodes.
• 7. Re: Creating random expression trees
<weeps/>

My bad! Every expression has an odd token size!
• 8. Re: Creating random expression trees
<weeps/>
My bad! Every expression has an odd token size!
ill let you redeem yourself: the number off all possible groupings is what sequence? (no googling!)
• 9. Re: Creating random expression trees
TuringPest wrote:
<weeps/>
My bad! Every expression has an odd token size!
ill let you redeem yourself: the number off all possible groupings is what sequence? (no googling!)
I'm going to give up straight away. I sucked at Combinatorics, and I'm usually pretty good at math. Feel free to belittle me. I didn't know there would be a quiz!
• 10. Re: Creating random expression trees
[catalan numbers|http://en.wikipedia.org/wiki/Catalan_number]

so in this case: trees = C( (n+1)/2 )

1 = 1
3 = 1
5 = 2
7 = 5
9 = 14
11 = 42
• 11. Re: Creating random expression trees
TuringPest wrote:
[catalan numbers|http://en.wikipedia.org/wiki/Catalan_number]
Groovy page!