分区一串括号

Question

任何人都可以帮我解决这个问题吗？我会输入问题,然后给出一些我的想法/替代解决方案.

所以问题就在于,给出一个这样的括号:

[[]]

我们希望为每个括号分配一个组号(组1或组2).一个有效的赋值意味着,如果你只看第一组中的括号,它会形成一个有效的,平衡的括号字符串(这就像[] [[]]之类的东西,而不是像[] [] []那样的东西.同样的对于第二组是正确的.组不必是连续的.我们想要计算将这些括号分成两组的方法.

在[[]]上面的示例字符串上,答案是6,这里是枚举:(1 =组1,2 =组2)

  [[]]
1.1111
2.2222
3.1221
4.2112
5.1212
6.2121

该安排不必包括所有组(如安排1.和2.)

思考

一个明显的暴力解决方案,最多可以使用32个括号,相当快速,是一个32位整数,表示哪个括号是单个组的一部分.或者我们可以使用数组.运行时间是O(2 ^ N)(我想),这太慢了？

通过查看问题,我认为您给出的原始括号字符串必须预先平衡,否则无法选择一个子集,使第1组和第2组平衡.

我还注意到你可以分开组件 - 字符串"[]"有2个排列,所以字符串"[] []"有4个排列.(您可以在每个组件中找到方法的数量并将它们相乘).

我对如何将这些想法纳入算法感到困惑.我写了蛮力程序,我检查了字符串"[]","[[]]","[[[]]]"和"[[[[]]]]",我不是真的看一个模式.

从将这些字符串插入我的暴力程序,我得到:

"[]" = 2
"[[]]" = 6
"[[]]" = 20
"[[[[]]]]" = 70

码:

char buf[1000];
int N;
bool isValid(int mask)
{
    int lv = 0;
    for (int i = 0; i < N; i++)
    {
        if (mask & (1 << i))
        {
            if (buf[i] == '(')
            {
                lv++;
            }
            else
            {
                lv--;
            }
            if (lv<0)
            {
                return false;
            }
        }
    }
    return lv==0;
}

int main() 
{
    scanf("%s", buf);
    N = strlen(buf);
    int ways = 0;
    for (int i = 0; i < (1 << N); i++)
    {
        if (isValid(i) && isValid(~i))
        {
            ways++;
        }
    }
    printf("Number of ways is %d\n", ways);
    return 0;
}

Answer 1

如果有任何帮助，对于像 [[[]]] 这样的“中心”字符串，您可以使用ways(1) = 2and ways(n) = ways(n-1)*(4*n-2)/n（或C(2n,n)如果您愿意的话）计算方式数，其中 n 是嵌套深度。

嵌套但不是“中心”的组（如 [[][]]）似乎遵循类似的模式，但我无法找出正确的公式。

编辑

我们的符号能力已经用完了，所以我将使用 texify 来表达数学公式。我想出了这样的事情：

周围组（您可以通过此更改公式）。