đếm boolean ngoặc đơn thực hiện

Question

Với biểu thức boolean có chứa các ký hiệu {true, false, và, hoặc, xor}, đếm số cách để ngoặc đơn biểu thức sao cho nó đánh giá đúng.

Ví dụ: chỉ có 1 cách để ngoặc đơn 'đúng và sai xor true' sao cho nó đánh giá đúng.

Đây là thuật toán của tôi

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. 

Chúng ta có thể có một giải pháp tốt hơn?

Answer 1

Mã giả của bạn cung cấp thuật toán trong O (2^n). Tôi nghĩ rằng bạn có thể có một cái gì đó trong O (n^3).

---

Trước hết, hãy xem sự phức tạp của thuật toán của bạn. Giả sử rằng số lượng hoạt động cần thiết để kiểm tra dấu ngoặc đơn là T(n). Nếu tôi hiểu rõ, thuật toán của bạn bao gồm:

• Cut biểu thức trong hai (n 1 khả năng)

• Kiểm tra xem bên trái và phần bên phải có parenthesization thích hợp.

Vì vậy 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

Một chút tính toán sẽ cho bạn biết rằng T(n) = 2^n*T(1) + O(n^2) = O(2^n)

---

Ý tưởng của tôi là t mũ những gì bạn chỉ cần là để kiểm tra cho ngoặc là "subwords". "Subword_i_j" bao gồm tất cả các phân đoạn giữa vị trí i và vị trí j. Tất nhiên, i<j, do đó bạn có N*(N-1)/2 từ khóa. Giả sử rằng L[i][j] là số lượng các dấu ngoặc đơn hợp lệ của subword_i_j. Để thuận tiện, tôi sẽ quên các giá trị khác M[i][j] cho biết số lượng dấu ngoặc đơn dẫn đến sai, nhưng đừng quên rằng nó ở đây!

Bạn muốn tính toán tất cả các từ khóa có thể bắt đầu từ các từ con nhỏ nhất (kích thước 1) thành số lớn nhất (cỡ N).

Bạn bắt đầu bằng cách tính toán L[i][i] cho tất cả i. Có N giá trị như vậy. Thật dễ dàng, nếu lần thứ i rác là True thì L[i][i]=1 khác L[i][i]=0. Bây giờ, bạn biết số lượng parenthesization cho tất cả subwords kích thước 1.

Cho phép nói rằng bạn biết parenthesization cho tất cả subwords kích thước S.

Sau đó tính toán L[i][i+S] cho i từ 1 đến N-S. Đây là các subwords có kích thước S + 1.Nó bao gồm tách từ con theo tất cả các cách có thể (cách S), và kiểm tra xem phần bên trái (là một từ có kích thước S1 < = S) và phần bên phải (có kích thước S2 < = S) và toán tử inbetween (hoặc, xor, và) tương thích. Có các giá trị S * (N-S) như vậy.

Cuối cùng, bạn sẽ kết thúc với L[1][N] sẽ cho bạn biết nếu có dấu ngoặc đơn hợp lệ.

Chi phí là:

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)

---

Lý do phức tạp là tốt hơn là trong mã giả của bạn, bạn kiểm tra nhiều lần cùng một subwords mà không lưu trữ kết quả trong bộ nhớ.

Chỉnh sửa: Arglllll, tôi đã bỏ qua câu we save all the solutions to subproblems and read them when we meet them again. thus save time.. Vâng, có vẻ như nếu bạn làm, bạn cũng có một thuật toán trong trường hợp xấu nhất O (N^3). Đừng nghĩ rằng bạn có thể làm tốt hơn nhiều so với ...

Answer 2

Vấn đề này có thể được giải quyết bằng cách Dynamic-Thuật toán và nó cũng tương tự như ma trận vấn đề chuỗi nhân, câu trả lời chi tiết là làm theo:

1, Let các hoạt động bao gồm a_i toán hạng và toán tử b_j (1 < = i < = n, 1 < = j < = n-1 n là kích thước của toán hạng), thay thế đúng cho 1, thay thế sai cho 0

2, Cho phép DPone [i] [j] là số cách để ngoặc đơn trong {a_i b_i a_i + 1 ... b_j-1 b_j} sao cho kết quả là 1, Cho phép DPzero [i] [j] là số cách để ngoặc đơn trong {a_i b_i a_i + 1 ... b_j-1 b_j} sao cho kết quả là 0

3 、 Tạo hàm hoạt động (i, j, k), giá trị trả về là số cách mà kết quả của hoạt động là 1 khi b_k là giá trị cuối cùng toán tử được sử dụng trong {a_i b_i a_i + 1 ... b_j-1 b_j}, phương thức hoạt động trực tiếp dựa trên b_k. Ví dụ, b_i là và, vì vậy giá trị trả về là DPone [i] [k] * DPone [k + 1] [j].

4, Bây giờ phương trình DP là làm theo:

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

vì vậy chúng tôi chỉ cần xác định DPone [1] [n]. Sự phức tạp là O (n^3)

Intention:

1, Chúng ta nên xác định DPzero [i] [j] sau khi xác định DPone [i] [j], nhưng nó đơn giản, DPzero [i ] [j] = total_Parenthesize_Ways [i] [j] -DPone [i] [j]

2 、 thứ tự tìm DPone là [1] [1], [2] [2], ... [ n] [n], [1] [2], [2] [3], ... [n-1] [n], [1] [3], [2] [4] ..... [2] [n], [1] [n], tất nhiên, [1] [1] ~ [n] [n] nên được khởi tạo bởi chính chúng ta.

Answer 3

Đây là mã để tính các dấu ngoặc đơn cho một mảng các toán tử và toán tử.

Thời gian phức tạp O (N^3) và không gian phức tạp 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]; 
}