计算布尔括号内的实现

Question

给定包含符号{true,false,和,或xor}的布尔表达式,计算括号表达式的方式的数量,使其计算结果为true.

例如,只有一种方法可以将'true和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)= checking if you cut at the first place+ checking if you cut at the second place+ ... +checking if you cut at the last place

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<j，你有N*(N-1)/2子词。假设这L[i][j]是 subword_i_j 的有效括号数量。为了方便起见，我会忘记其他M[i][j]表示导致 false 的括号数量的值，但不要忘记它就在这里！

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

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

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

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

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

费用是：

checking subwords of size 1+ checking subwords of size 2+ ... +checking subwords of size N

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

=O(N^3)

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

编辑：Argllllll，我忽略了这句话we save all the solutions to subproblems and read them when we meet them again. thus save time.。好吧，看来如果你这样做了，你也有一个最坏情况 O(N^3) 的算法。不要认为你能做得比这更好......