Parentheses

Parentheses

I'm working on this program to generate a series of variations of an expression to see if we can generate all the numbers in the world, or at least these up to 11,000 or so. So I am writting an expression generator and I have written expression evaluator to evaluate the expression generated by the expression generator and that all seems to be working fine. But so for we don't have any parentheses. As you know, if you have ever mucked around with algebra or computer programming, parentheses can dramatically change the value of an expression. The problem seemed simple enough, all you have to do is take your expression and then combine it with each of the possible combinations of parentheses that can be applied to it. If you only have 2 elements, like A + B, no amount of parenthesizing is going to affect the value of this expression. When you have 3 elements, there are three combinations, one with no parentheses: A + B x C, or one where you enclose and A + B and another where you enclose B x C. With four elements it starts to get complex and when you get to 9 which is where I am heading it's downright complicated.

For 9 elements, there are

• 8 ways to enclose 2 elements
• 7 ways to enclose 3 elements
• 6 ways to enclose 4 elements
• 5 ways to enclose 5 elements
• 4 ways to enclose 6 elements
• 3 ways to enclose 7 elements
• 2 ways to enclose 8 elements

For a total of 35 ways, and that is with only one single set of parentheses. Now inside of each of those groups of 3 elements, there are three ways to further affect those parentheses, as we saw above, so that means 7 times 3. I don't know how many this is going to get to, but it's going to be on the order of hundreds.

So here's how I am going to generate all these combinations of parentheses.

Top level, we run through all of the items listed above. Then for each of those cases, we divide our task in three, one for subdividing what's inside of the parentheses, and one for subdividing the elements before the parentheses and one for after. There is going to be some simple reduction here. We cannot subdivided a group of two elements, two is as low as we can go. And if we have enclosed 8 elements, then there is only one element left over, and putting parentheses around that won't help.

I've been thinking about this, off and on, all afternoon. I just hope this explanation will be as clear in the morning as it is now.

Update next day. I figured out how many different ways parentheses can be applied to an expression containing a few elements:

There are 603 ways parentheses can be to an expression containing 9 elements.