F**********r
发帖数: 237 | 1 矩阵链式相乘加括号，生成所有legal的combination.
according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？ |
x******g
发帖数: 41 | |
g***s
发帖数: 3811 | 3 http://baike.baidu.com/view/1154333.html#sub1154333
http://www.cppblog.com/zhgw01/archive/2008/06/05/52306.aspx
【在 F**********r 的大作中提到】
: 矩阵链式相乘加括号，生成所有legal的combination.
: according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
: (A1(A2(A3A4)))
: (A1((A2A3)A4))
: ((A1A2)(A3A4))
: ((A1(A2A3))A4)
: (((A1A2)A3)A4)
: 想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？
|
O******n
发帖数: 1505 | 4 什么叫legal。。。不是只要顺序不变，随便怎么结合律么
【在 F**********r 的大作中提到】
: 矩阵链式相乘加括号，生成所有legal的combination.
: according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
: (A1(A2(A3A4)))
: (A1((A2A3)A4))
: ((A1A2)(A3A4))
: ((A1(A2A3))A4)
: (((A1A2)A3)A4)
: 想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？
|
O******n
发帖数: 1505 | 5 等价于
n个叶子的二叉树有多少种
【在 F**********r 的大作中提到】
: 矩阵链式相乘加括号，生成所有legal的combination.
: according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
: (A1(A2(A3A4)))
: (A1((A2A3)A4))
: ((A1A2)(A3A4))
: ((A1(A2A3))A4)
: (((A1A2)A3)A4)
: 想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？
|
m********l
发帖数: 4394 | 6 不就是double penetration嘛
好像是把最大的先搞定
【在 F**********r 的大作中提到】
: 矩阵链式相乘加括号，生成所有legal的combination.
: according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
: (A1(A2(A3A4)))
: (A1((A2A3)A4))
: ((A1A2)(A3A4))
: ((A1(A2A3))A4)
: (((A1A2)A3)A4)
: 想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？
|
F**********r
发帖数: 237 | 7 就是说比如((A1)(A2)(A3)(A4))虽然也能parse，但是不count
【在 O******n 的大作中提到】
: 什么叫legal。。。不是只要顺序不变，随便怎么结合律么
|
F**********r
发帖数: 237 | 8 什么看错了？
【在 x******g 的大作中提到】
: 看错啦。。。。
|
F**********r
发帖数: 237 | |
h*********3
发帖数: 111 | 10 憋了老半天，写了一个，现在脑袋是真的不好使了。。。
算是抛砖引玉了。。。
void DoCatalan(vector &buf,vector &catalanStack)
{
string tmp,left,backup,backup2;
if ( buf.size() == 1 )
{
tmp = buf[0];
for ( int i=catalanStack.size()-1;i>=0;i--)
{
left = catalanStack[i];
tmp = left + tmp + ")";
}
cout << tmp << endl;
return;
}
if ( catalanStack.size() == 0 )
{
backup = buf[buf.size()-1];
tmp = "(" + backup;
buf.pop_back();
catalanStack.push_back(tmp);
DoCatalan(buf,catalanStack);
catalanStack.pop_back();
buf.push_back(backup);
}
else
{
// first try: push the stack
backup = buf[buf.size()-1];
tmp = "(" + backup;
buf.pop_back();
catalanStack.push_back(tmp);
DoCatalan(buf,catalanStack);
// restore the original stack and buf
catalanStack.pop_back();
buf.push_back(backup);
// then try: pop the stack
backup = catalanStack[catalanStack.size()-1];
catalanStack.pop_back();
backup2 = buf[buf.size()-1];
buf.pop_back();
left = backup + backup2 + ")";
buf.push_back(left);
DoCatalan(buf,catalanStack);
// restore the stack and buf
catalanStack.push_back(backup);
buf.pop_back();
buf.push_back(backup2);
}
}
void Catalan(char arr[],int len)
{
if ( !arr || len <= 1 )
return;
vector catalanStack;
vector buf;
string tmp;
for ( int i=len-1;i>=0;i--)
{
tmp.clear();
tmp.push_back(arr[i]);
buf.push_back(tmp);
}
DoCatalan(buf,catalanStack);
}
==========================
调用如下：
Catalan("abcd",4);
【在 F**********r 的大作中提到】
: 矩阵链式相乘加括号，生成所有legal的combination.
: according to Introduction to algorithms, A1*A2*A3*A4只有5种legal output:
: (A1(A2(A3A4)))
: (A1((A2A3)A4))
: ((A1A2)(A3A4))
: ((A1(A2A3))A4)
: (((A1A2)A3)A4)
: 想了很久不知道怎么能方便的break down，而且这个加括号的rule到底是什么呢？
|
