recuento boolean parenthesizations implementación

Question

Dada una expresión booleana que contenga los símbolos {true, false y, o, xor}, cuente el número de maneras de poner en paréntesis la expresión de modo que se evalúe como verdadera.

Por ejemplo, solo hay 1 forma de paréntesis 'verdadero y falso xo verdadero' de tal manera que se evalúa como verdadero.

Aquí está mi algoritmo

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. 

podemos tener una mejor solución?

Answer 1

Su pseudocódigo da un algoritmo en O (2^n). Creo que puedes tener algo en O (n^3).

---

En primer lugar, vamos a ver la complejidad de su algoritmo. Digamos que el número de operaciones necesarias para verificar la paréntesis es T(n). Si he entendido bien, su algoritmo consiste en:

• Corte la expresión en dos (n-1 posibilidades)

• Compruebe si la izquierda y la parte derecha tienen parentización apropiado.

Así 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) + ... + n + T(n-1)+T(1)

Un poco de cálculo le dirá T(n) = 2^n*T(1) + O(n^2) = O(2^n)

---

Mi idea es t Lo que solo necesita es comprobar si hay paréntesis entre las "subpalabras". El "subword_i_j" consiste en todos los literales entre la posición i y la posición j. Por supuesto, i<j, por lo que tiene 0:subwords. Digamos que L[i][j] es el número de paréntesis válidos de la subpalabra_i_j. Por comodidad, olvidaré los otros valores M[i][j] que indican el número de paréntesis que conduce a falso, ¡pero no olvide que está aquí!

Quiere calcular todas las subwords posibles empezando desde las más pequeñas (tamaño 1) hasta la más grande (tamaño N).

Usted comienza por calcular L[i][i] para todos los i. Hay N tales valores. Es fácil, si el i-th litteral es verdadero, entonces L[i][i]=1 else L[i][i]=0. Ahora, se conoce el número de parentización para todas las palabras parciales de tamaño 1.

que permite decir que conoce el parentización para todas las palabras parciales de la talla S.

después calcular L[i][i+S] para i entre 1 y N-S. Estas son palabras secundarias de tamaño S + 1.Consiste en dividir la subpalabra de todas las maneras posibles (formas S), y comprobando si la parte izquierda (que es una subpalabra del tamaño S1 < = S) y la parte derecha (que es del tamaño S2 < = S) y el operador entre (o, xor, y) son compatibles. Hay S * (N-S) tales valores.

Finalmente, terminará con L[1][N] que le dirá si hay un paréntesis válido.

El costo es:

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)

---

La razón por la que la complejidad es mejor es que en su pseudocódigo, comprueba varias veces las mismas subwords sin almacenar el resultado en la memoria.

Editar: Arglllll, pasé por alto la oración we save all the solutions to subproblems and read them when we meet them again. thus save time.. Bueno, parece que si lo haces, también tienes un algoritmo en el peor de los casos O (N^3). No creo que se puede hacer mucho mejor que eso ...

Answer 2

Este problema puede ser resuelto por Dynamic-Algoritmo y es similar a Matrix problema de multiplicación de la cadena, el detalle respuesta es seguir:

1, Let la operación consiste en a_i operando y b_j operador (1 < = i < = n, 1 < = j < = n-1 n es el tamaño de operando), sustituir cierto para 1, sustituto falsa para 0

2, Deje que DPone [i] [j] sea el número de formas de paréntesis en {a_i b_i a_i + 1 ... b_j-1 b_j} de modo que el resultado sea 1, deje que DPzero [i] [j] sea el número de formas para paréntesis en {a_i b_i a_i + 1 ... b_j-1 b_j} tal que el resultado es 0

3, función de construcción oper (i, j, k), el valor de retorno es el número de formas en que el resultado de la operación es 1 cuando b_k es el último operador usado en {a_i b_i a_i + 1 ... b_j-1 b_j}, el método de operación directa se basa en b_k. Por ejemplo, b_i es y, entonces, el valor de retorno es DPone [i] [k] * DPone [k + 1] [j].

4, Ahora la ecuación DP es seguir:

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

así que solo necesitamos determinar DPone [1] [n]. La complejidad es O (n^3)

Intención:

1, debemos determinar DPzero [i] [j] después de determinar DPone [i] [j], pero es simple, DPzero [i ] [j] = total_Parenthesize_Ways [i] [j] -DPone [i] [j]

2, el orden para encontrar DPone es [1] [1], [2] [2], ... [ n] [n], [1] [2], [2] [3], ... [n-1] [n], [1] [3], [2] [4] ..... . [2] [n], [1] [n], por supuesto, [1] [1] ~ [n] [n] debería ser inicializado por nosotros mismos.

Answer 3

Aquí está el código para contar paréntesis para una matriz de booleanos y operadores.

Complejidad de tiempo O (n^3) y el espacio complejidad 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]; 
}