General all possible expression trees

This topic is 4595 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I would like to enumerate/generate all possible expression trees from expressions like "1+2*3-8". My idea goes something like: generateExpressions: for each operator in expression leftExpressionLists = generateExpressions( subexpression-left-of-operator) rightExpressionLists = generateExpressions( subexpression-right-of-operator) combinedExpressionLists = combineAllPermutations( leftExpressionLists, rightExpressionLists ) But, this seems non-trivial for a quiz problem. There must be some trick for a simpler algorithm?

Share on other sites
I think this is the result you are looking for. There are 5 of them in this case. I assume that you want to know how to write a program to produce these?
   *            +              +                  -              - +   -         1  *           1    -            *  8         +    81 2 3 8          2  -            *  8         +  3          1  *                   3 8          2 3          1 2              2 3
Edit: I did post the answer, but I have removed it, as I need you to confirm that this isn't homework of some kind first.

Share on other sites
I think we are speaking of the same straight-forward recursive method that I briefly outlined.

Thus now we are just looking for better ways, which is purely optional though self motivated.

• 9
• 23
• 10
• 19