ブール括弧の数を数える実装

Question

{true、false、and、or xor}の記号を含むブール式を指定すると、式をかっこにして真と評価する方法の数を数えます。

たとえば、 '真と偽のxor true'を括弧でくくって真と評価する方法は1つしかありません。ここで

は私のアルゴリズム

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)であるとします。

• カット2（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)

ことを教えてくれます

---

私の考えはtですあなたが必要とするのは括弧が "サブワード"かどうかをチェックすることだけです。 "subword_i_j"は、位置iと位置jとの間のすべてのリテラルからなる。もちろんi<jですので、N*(N-1)/2サブワードがあります。 L[i][j]がsubword_i_jの有効なかっこの数であるとします。便宜上、私は他の値M[i][j]を忘れてしまいますが、これはカッコの数がfalseになることを示していますが、ここにあることを忘れないでください！

最小のもの（サイズ1）から最大サイズ（サイズN）までのすべての可能なサブワードを計算します。

すべてのiに対してL[i][i]を計算します。そのようなN個の値があります。簡単なことですが、i番目のlitteralがTrueの場合は、L[i][i]=1以外のL[i][i]=0です。さて、あなたはサイズ1

の全てのサブワードのためのカッコの数はあなたがサイズS

の全てのサブワードのためのカッコは、その後1およびN-S間のiについてL[i][i+S]を計算知っていると言うことができます知っています。これらはサイズS + 1のサブワードです。サブワードをすべての可能な方法（S方法）で分割することから成ります。と左部分（サブサイズS1 < = S）との右側部分（サイズはS2 < = S ）との間の演算子（または、xor、および）は互換性があります。 S *（N-S）という値があります。

最後に、L[1][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)

= O(N^3)

---

複雑さがより良い理由は、擬似コードでは、結果をメモリに格納せずに同じサブワードを何度もチェックすることです。

編集：Arglllll、私は文we save all the solutions to subproblems and read them when we meet them again. thus save time.を見落としました。まあ、もしそうなら、あなたは最悪のケースのO（N^3）でもアルゴリズムを持っているようです。 、

1をしてみましょう：あなたはそれよりもはるかに良いを行うことができるとは思わない...

Answer 2

をこの問題は、ダイナミック・アルゴリズムによって解決することができ、連鎖乗算問題を行列に類似しており、詳細な答えは以下の通りです動作は、1 0

2の代替偽の真置換、オペランドa_iをオペレータb_j（1 < = I < = N = J < = N-1、N 1 <は、オペランドのサイズである）から成りますDPone [i] [j]は、結果が1となるように{a_i b_i a_i + 1 ... b_j-1 b_j}を括弧でくくる方法の数とする。DPzero [i] [j] {a_i b_i a_i + 1}をカッコで囲む...、b_j-1 b_j}結果が0になるようにする。

3、ビルド関数oper（i、j、k）、戻り値は、b_kが最後のときの演算の結果が1になるウェイ数{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] =最大{SUM（OPER（I、J、K））I < = K < = J-1}

したがって、DPone [1] [n]を決定するだけで済みます。 [I] [J]

1、我々はDPzeroを決定する必要があります後DPone [i]の[j]を決定し、それは簡単です、DPzero [I：複雑さはO（N^3）

意向でありますDPoneが[1]、[2] [2]、... [1]、[2] [2]、... [ n] [n]、[1] [2]、[2] [3]、... [n-1] [n]、[1] [3]もちろん[1] [1]〜[n] [n]は自分で初期化する必要があります。[2] [n]、[1] [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]; 
}