Wednesday, July 25, 2007

Show that a full parenthesization of an n-element expression has exactly n - 1 pairs of parentheses.

如果n=1,只有一个元素,无需括号,所以有n-1个pair(1)
如果n小于l,这时有n-1个对 (2)
当 n=l,假设 1<=k 小于n,n个表达式可以分为e1..ek 和ek+1..en两个子表达式。分别有k-1和n-k-1个对,共n-2个对,加上e1..ek 和ek+1..en两个子表达式形成的对,这时有n-1个对。

No comments: