Подсчет выполнения логических скобок

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

Например, существует только один способ вставить в скобки "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.

У нас есть лучшее решение?

Ответы

Ответ 1

Ваш псевдокод дает алгоритм в O (2 ^ n). Я думаю, что у вас может быть что-то в O (n ^ 3).

Прежде всего, рассмотрим сложность вашего алгоритма. Скажем, что количество операций, необходимых для проверки скобок, T(n). Если я правильно понял, ваш алгоритм состоит из:

Вырежьте выражение в двух вариантах (n-1)
Убедитесь, что левая и правая части имеют соответствующую скобку.

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) + n

Немногочисленные вычисления скажут вам, что T(n) = 2^n*T(1) + O(n^2) = O(2^n)

Моя идея заключается в том, что вам нужно только проверять наличие в скобках "подслов". "Subword_i_j" состоит из всех литтеров между позицией я и позицией j. Конечно, i<j, поэтому у вас есть подтексты N*(N-1)/2. Скажем, что L[i][j] - это число допустимых скобок подслова_i_j. Для удобства я забуду другие значения M[i][j], в которых указано число скобок, которое приводит к ложному, но не забывайте, что он здесь!

Вы хотите вычислить все возможные подзаголовки, начиная с самых маленьких (размер 1) до самого большого (размер N).

Вы начинаете с вычисления L[i][i] для всех i. Существует N таких значений. Это легко, если i-й литтера имеет значение True, тогда L[i][i]=1 else L[i][i]=0. Теперь вы знаете число скобок для всех подслов размером 1.

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

Затем вычислите L[i][i+S] для я между 1 и N-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). Не думайте, что вы можете сделать намного лучше, чем это...

Ответ 2

Вот код для подсчета скобок для массива логических операторов и операторов.

Сложность времени 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];
}

Ответ 3

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

1, пусть операция состоит из операнда a_i и оператора b_j (1 <= я <= n, 1 <= j <= n-1 n - размер операнда), заменить значение true для 1, заменить false для 0

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, Build function oper (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)) я <= k <= j-1}

поэтому нам просто нужно определить DPone [1] [n]. Сложность 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],... [n] [n], [1] [2], [2] [3]... [n-1] [n], [1] [3], [2] [4]...... [2] [n], [1] [n], конечно, [1] [1] ~ [n] [n] должны быть инициализированы сами.