подсчет реализации булевых скобок

Question

Учитывая логическое выражение, содержащее символы {true, false и, или, xor}, подсчитайте количество способов заключить выражение в скобки так, чтобы оно получило значение true.

Например, есть только 1 способ заключить в скобки '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 (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];
}

Answer 2

Ваш псевдокод дает алгоритм в 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]=1 else L[i][i]=0.Теперь вы знаете число скобок для всех подслов размера 1.

Допустим, вы знаете скобки для всех подслов размера S.

Затем вычислите L[i][i+S] для i между 1и NS.Это подслова размера S + 1.Он состоит из разбиения подслова всеми возможными способами (S-способы), и проверки, является ли левая часть (которая является подсловом размера S1 <= S) <strong>и правой частью (который имеет размер S2 <= S) <strong>и , операторы между (или, xor, и) совместимы.Есть S * (NS) таких значений.

Наконец, вы получите 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).Не думай, что ты сможешь добиться гораздо большего ...

Answer 3

Эта проблема может быть решена с помощью динамического алгоритма и аналогична задаче умножения цепочки матриц, подробный ответ следующий:

1 、 Пусть операция состоит из операнда a_i и оператора b_j (1 <=i <= n, 1 <= j <= n-1 n - размер операнда), замените true на 1, замените false на 0 </p>

2 、 Пусть DPone [i] [j] будет числомспособов заключить в скобки {a_i b_i a_i + 1 ... b_j-1 b_j} так, чтобы результат составил 1, пусть DPzero [i] [j] будет количеством способов заключить в скобки {a_i b_i a_i + 1 ... b_j-1 b_j} такой, что результат равен 0

3 o Оператор функции построения (i, j, k), возвращаемое значение - это число способов, при которых результат операции равен 1, когда b_k является последнимиспользуемый оператор в {a_i b_i a_i + 1 ... b_j-1 b_j}, метод прямой операции основан на b_k.Например, b_i есть и, поэтому возвращаемое значение - DPone [i] [k] * DPone [k + 1] [j].

4 、 Теперь уравнение DP выглядит следующим образом:

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

, поэтому нам просто нужно определитьDPone [1] [п].Сложность O (n ^ 3)

Намерение:

1 、 Мы должны определить DPzero [i] [j] после определения DPone [i] [j], но это просто, DPzero [i] [j] = total_Parenthesize_Ways [i] [j] -DPone [i] [j]

2 、 порядок поиска DPone: [1] [1], [2] [2], ... [п] [п], [1] [2], [2] [3], ... [п-1] [п], [1] [3], [2] [4] ...... [2] [n], [1] [n], конечно, [1] [1] ~ [n] [n] должны быть инициализированы нами.