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

$\displaystyle A_n = \sum_{i=1}^{n-1} A_iA_{n-i}$ ; $\displaystyle 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 $\displaystyle C_n$ ways of parenthesizing them, where $\displaystyle C_n$ is the n-th Catalan number. Catalan number - Wikipedia, the free encyclopedia