由网友(好小伙潇潇洒洒@)分享简介：由于包含符号{真，假，与，或，异或}一个布尔EX pression，计数的方式来圆括号前pression，使得它的计算结果为true的数量。Given a boolean expression containing the symbols {true, false, and, or, xor}, count the...

由于包含符号{真，假，与，或，异或}一个布尔EX pression，计数的方式来圆括号前pression，使得它的计算结果为true的数量。

Given a boolean expression containing the symbols {true, false, and, or, xor}, count the number of ways to parenthesize the expression such that it evaluates to true.

例如，只有1路到圆括号真假异真，使得它的计算结果为真。

For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to 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.

我们能有一个更好的解决方案？

Can we have a better solution?

推荐答案

您的伪code给出O型算法（2 ^ n）的。我想你可以有东西在为O（n ^ 3）。

首先，让我们看看你的算法的复杂性。比方说，检查加括号所需的操作数 T（N）。如果我深知，你的算法包括：

First of all, let's see the complexity of your algorithm. Let's say that the number of operations needed to check the parenthesization is T(n). If I understood well, your algorithm consists of :

切前pression两个（N-1的可能性）

Cut the expression in two (n-1 possibilities)

检查左，右部有相应的加括号。

Check if the left and the right part have appropriate parenthesization.

所以 T（N） = 检查，如果你砍在首位 + 检查，如果你砍在第二位 + ... + 检查，如果你砍在最后的地方

So 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） + ñ

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之间的所有litterals的。当然， I＆LT;Ĵ让你有 N *（N-1）/ 2 子字。比方说， L [I] [J] 是subword_i_j有效parenthesizations的数量。为方便起见，我会忘记其他值 M [I] [J] ，指出导致错误的括号的数量，但不要忘记，它在这里！

My idea is that what you only need is to check for parenthesization are the "subwords". The "subword_i_j" consists of all the litterals between position i and position j. Of course i<j so you have N*(N-1)/2 subwords. Let's say that L[i][j] is the number of valid parenthesizations of the subword_i_j. For the sake of convenience, I'll forget the other values M[i][j] that states the number of parenthesization that leads to false, but don't forget that it's here!

您要计算所有可能的子字从最小的人（尺寸1）最大的一个（大小为N）开始。

You want to compute all the possible subwords starting from the smallest ones (size 1) to the biggest one (size N).

您首先计算 L [I] [I] 对于所有的i。有N个这样的值。这很容易，如果第i个litteral为真，那么 L [I] [I] = 1 其他 L [I] [I] = 0 。现在，你知道加括号的尺寸为1的所有子字的数量。

You begin by computing L[i][i] for all i. There are N such values. It's easy, if the i-th litteral is True then L[i][i]=1 else L[i][i]=0. Now, you know the number of parenthesization for all subwords of size 1.

比方说，你知道的加括号的大小为S的所有子字。

Lets say that you know the parenthesization for all subwords of size S.

然后计算 L [I] [I + S] 为1至NS我。这是大小S + 1的子字。它由分裂子字在所有可能的方式（S方式），和检查是否左边部分（这是大小的子字S1＆LT; = S）和的权利部分（这是大小S 2＆LT; = S）和操作插图中（或，异或，与）是兼容的。有S *（N-S）这样的值。

Then compute L[i][i+S] for i between 1 and N-S. These are subwords of size S+1. It consists of splitting the subword in all possible ways (S ways), and checking if the left part(which is a subword of size S1<=S) and the right part(which is of size S2<=S) and the operator inbetween (or, xor, and) are compatible. There are S*(N-S) such values.

最后，你将最终获得 L [1] [N] 它会告诉你，如果有一个有效的加括号。

Finally, you'll end up with L[1][N] which will tell you if there is a valid parenthesization.

的代价是：

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

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）

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

= O（N ^ 3）

原因的复杂性是较好的是，在你的伪code，检查多次相同的子字没有把结果存储在内存中。

The reason the complexity is better is that in your pseudocode, you check multiple times the same subwords without storing the result in memory.

编辑：Arglllll，我忽略了一句我们所有的解决方案保存到子问题，并宣读他们当我们再次见到他们。从而节省了时间。。嗯，看来，如果你这样做，你也有在最坏情况下O（N ^ 3）的算法。不要以为你可以做得比这更好的......

Edit : Arglllll, I overlooked the sentence we save all the solutions to subproblems and read them when we meet them again. thus save time.. Well, seems that if you do, you also have an algorithm in worst-case O(N^3). Don't think you can do much better than that...