计算布尔括号的实现

Question

给定一个包含符号 {true、false、and、or、xor} 的布尔表达式，计算将表达式添加括号以使其计算结果为 true 的方式的数量。

例如，只有一种方法可以将“true and false xor true”括起来，使其计算结果为 true。

这是我的算法

we can calculate the total number of parenthesization of a string
Definition:  
N - the total number of 
True -  the number of parenthesizations that evaluates to true
False - the number of parenthesizations that evaluates to false
True + False = N 
Left_True - the number of parenthesization in the left part that evaluates to True
same to Left_False, Right_True, Right_False

we iterate the input string from left to right and deal with each operator as follows:


if it is "and", the number of parenthesization leads to true is
    Left_True * Right_True;

if it is "xor", the number of parenthesization leads to true
    Left_True * Right_False + Left_False * Right_True

if it is 'or', the number is
    N - Left_False * Right_False 

Here is my psuedocode 

n = number of operator within the String 

int[n][n] M; // save number of ways evaluate to true

for l = 2 to n
for i = 1 to n-l+1
  do j = i+l-1  
  // here we have different string varying from 2 to n starting from i and ending at j
  for k = i to j-1
  // (i,k-1) is left part
  // (k+1, j) is right part
  switch(k){
    case 'and':  // calculate, update array m
    case 'or':  // same
    case 'xor':
  }

  we save all the solutions to subproblems and read them when we meet them again. thus save time.

我们可以有更好的解决方案吗？

Answer 1

您的伪代码给出了 O(2^n) 的算法。我认为你可以在 O(n^3) 内得到一些东西。

---

首先，让我们看看你的算法的复杂性。假设检查括号所需的运算次数为 T(n)。如果我理解得很好，你的算法包括：

• 将表达式切成两部分（n-1种可能性）

• 检查左侧和右侧部分是否有适当的括号。

所以 T(n) = 检查是否在第一个位置剪切 + 检查是否在第二个位置剪切 + ... + < code>检查是否在最后一个地方剪切

T(n) = T(1)+T(n-1) + T( 2)+T(n-2) + ... + T(n-1)+T(1) + n

稍微计算一下就会知道 T(n) = 2^n*T(1) + O(n^2 ) = O(2^n)

---

我的想法是，您只需要检查括号是“子词”。 “subword_i_j”由位置 i 和位置 j 之间的所有文字组成。当然，i 所以你有 N*(N-1)/2 个子词。假设 L[i][j] 是 subword_i_j 的有效括号数量。为了方便起见，我会忘记其他值 M[i][j] ，这些值表示导致 false 的括号数量，但不要忘记它就在这里！

您想要计算所有可能的子词，从最小的子词（大小 1）到最大的子词（大小 N）。

首先计算所有 i 的 L[i][i]。有N个这样的值。这很简单，如果第 i 个字符串为 True，则 L[i][i]=1 否则 L[i][i]=0。现在，您知道所有大小为 1 的子字的括号数量。

假设您知道所有大小为 S 的子字的括号数量。

然后计算 L[i][i+S] 之间的 i 1 和 NS。这些是大小为 S+1 的子字。它包括以所有可能的方式（S 方式）拆分子词，并检查左侧部分（即大小为 S1<=S 的子词）和是否位于右侧部分（大小为 S2<=S）和之间的运算符（或、异或和）是兼容的。有S*(NS)这样的值。

最后，您将得到 L[1][N] ，它会告诉您是否存在有效的括号。

成本为：

检查大小为 1 的子字 + 检查大小为 2 的子字 + ... + 检查大小为 N 的子字

= N + N-1 + 2*(N-2) + 2*(N-2) + .. + (N-1)*(1)

= O(N^3)

---

复杂性更好的原因是，在伪代码中，您多次检查相同的子词，而无需将结果存储在内存中。

编辑：Argllllll，我忽略了这句话我们保存子问题的所有解决方案，并在我们再次遇到它们时阅读它们。从而节省时间。。好吧，看来如果你这样做了，你也有一个最坏情况 O(N^3) 的算法。不要认为你能做得比这更好......

Answer 2

该问题可以通过动态算法解决，类似于矩阵链乘法问题，详细答案如下：

1、设操作数由操作数 a_i 和运算符 b_j 组成（1<=i<=n, 1<=j< ;=n-1 n 为操作数的大小），用 true 代替 1，用 false 代替 0

2、设 DPone[i][j] 为方法数在 {a_i b_i a_i+1 ... b_j-1 b_j} 中添加括号，使得结果为 1，令 DPzero[i][j] 为在 {a_i b_i a_i+1 ... b_j- 中添加括号的方式数1 b_j} 使得结果为 0

3、构建函数 oper(i,j,k)，返回值为使得运算结果为 1 的方式的个数b_k是{a_i b_i a_i+1 ... b_j-1 b_j}中最后使用的运算符，直接运算方法以b_k为基础。例如b_i为and，则返回值为DPone[i][k]*DPone[k+1][j]。

4、现在DP方程如下：

DPone[i][j] = max{ sum ( oper(i,j,k) ) i<=k<=j-1 }

所以我们就需要确定DPone[1][n]。复杂度为 O(n^3)

意图：

1、确定 DPone[i][j] 后，再确定 DPzero[i][j]，但很简单，DPzero[i][j] ]=total_Parenthesize_Ways[i][j]-DPone[i][j]

2、查找DPone的顺序为[1][1],[2][2],...[n][n],[1][2],[2][3],...[n-1][n], [1][3],[2][4]......[2][n],[1][n]，当然，[1][1]~[n][n]应该由我们自己初始化。

Answer 3

下面是计算布尔值和运算符数组的括号数量的代码。

时间复杂度O(N^3)和空间复杂度O(N^2)

public static int CountingBooleanParenthesizations(bool[] boolValues, string[] operators)
{
    int[,] trueTable = new int[boolValues.Length, boolValues.Length];
    int[,] falseTable = new int[boolValues.Length, boolValues.Length];
    for (int j = 0; j < boolValues.Length; j++)
    {
        for (int i = j; i >= 0; i--)
        {
            if (i == j)
            {
                trueTable[i, j] = boolValues[i] ? 1 : 0;
                falseTable[i, j] = boolValues[i] ? 0 : 1;
            }
            else
            {
                int trueSum = 0;
                int falseSum = 0;
                for (int k = i; k < j; k++)
                {
                    int total1 = trueTable[i, k] + falseTable[i, k];
                    int total2 = trueTable[k + 1, j] + falseTable[k + 1, j];
                    switch (operators[k])
                    {
                        case "or":
                            {
                                int or = falseTable[i, k] * falseTable[k + 1, j];
                                falseSum += or;
                                or = total1 * total2 - or;
                                trueSum += or;
                            }
                            break;
                        case "and":
                            {
                                int and = trueTable[i, k] * trueTable[k + 1, j];
                                trueSum += and;
                                and = total1 * total2 - and;
                                falseSum += and;
                            }
                            break;
                        case "xor":
                            {
                                int xor = trueTable[i, k] * falseTable[k + 1, j] + falseTable[i, k] * trueTable[k + 1, j];
                                trueSum += xor;
                                xor = total1 * total2 - xor;
                                falseSum += xor;
                            }
                            break;
                    }
                }
                trueTable[i, j] = trueSum;
                falseTable[i, j] = falseSum;
            }
        }
    }
     return trueTable[0, boolValues.Length - 1];
}