1. ## Equation Evaluator

Given a number of terms, n in an equation containing only addition as the only possible operator, find the different number of valid ways in which they can be evaluated. Order of evaluation is controlled by grouping the terms in brackets

e.g. if n = 4
it means that there are 4 terms in the equation – i.e. something like
a+b+c+d

Now the valid ways in which it can be evaluated :
(a + (b + (c+d)))
(a + ((b+c) + d))
((a+b) + (c+d))
(((a+b) + c) + d)
((a + (b+c)) + d)

So the answer in this case is 5

whats the logic for this problem?

2. Originally Posted by suditi
Given a number of terms, n in an equation containing only addition as the only possible operator, find the different number of valid ways in which they can be evaluated. Order of evaluation is controlled by grouping the terms in brackets

e.g. if n = 4
it means that there are 4 terms in the equation – i.e. something like
a+b+c+d

Now the valid ways in which it can be evaluated :
(a + (b + (c+d)))
(a + ((b+c) + d))
((a+b) + (c+d))
(((a+b) + c) + d)
((a + (b+c)) + d)

So the answer in this case is 5

whats the logic for this problem?
I'm not sure. But I think all you are trying to construct structurally different binary trees with 4 (or more generally n end nodes)

So is there a formula for that? Does it match to the answer you are expecting?

3. Originally Posted by aman_cc
I'm not sure. But I think all you are trying to construct structurally different binary trees with 4 (or more generally n end nodes)

So is there a formula for that? Does it match to the answer you are expecting?

Yes - It works. (atleast for some initial cases)

I have the recursive formula

$A_n = \sum_{i=1}^{n-1} A_iA_{n-i}$ ; $A_1=1$

So using this we get A2=1, A3=2, A4=5
(Not sure how to put this as a function of 'n' though)

4. If you have n terms there are $C_n$ ways of parenthesizing them, where $C_n$ is the n-th Catalan number. Catalan number - Wikipedia, the free encyclopedia