Рубрики

Проблема булевых скобок | DP-37

Дано логическое выражение со следующими символами.

Symbols
    'T' ---> true 
    'F' ---> false 

И следующие операторы заполнены между символами

Operators
    &   ---> boolean AND
    |   ---> boolean OR
    ^   ---> boolean XOR 

Подсчитайте количество способов, которыми мы можем заключить выражение в скобки, чтобы значение выражения было равно true.

Пусть вход имеет форму двух массивов: один содержит символы (T и F) по порядку, а другой содержит операторы (&, | и ^}

Примеры:

Input: symbol[]    = {T, F, T}
       operator[]  = {^, &}
Output: 2
The given expression is "T ^ F & T", it evaluates true
in two ways "((T ^ F) & T)" and "(T ^ (F & T))"

Input: symbol[]    = {T, F, F}
       operator[]  = {^, |}
Output: 2
The given expression is "T ^ F | F", it evaluates true
in two ways "( (T ^ F) | F )" and "( T ^ (F | F) )". 

Input: symbol[]    = {T, T, F, T}
       operator[]  = {|, &, ^}
Output: 4
The given expression is "T | T & F ^ T", it evaluates true
in 4 ways ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) 
and (T|((T&F)^T)). 

Решение:
Пусть T (i, j) представляет количество способов заключить в скобки символы между i и j (оба включительно), так что подвыражение между i и j оценивается как true.

<! —

->

Пусть F (i, j) представляет количество способов заключить в скобки символы между i и j (оба включительно), так что подвыражение между i и j оценивается как ложное.


<! —

->
Базовые случаи:

T(i, i) = 1 if symbol[i] = 'T' 
T(i, i) = 0 if symbol[i] = 'F' 

F(i, i) = 1 if symbol[i] = 'F' 
F(i, i) = 0 if symbol[i] = 'T'

Если мы нарисуем рекурсивное дерево выше рекурсивного решения, мы можем заметить, что оно много перекрывающихся подзадач. Как и другие проблемы динамического программирования , ее можно решить, заполнив таблицу снизу вверх. Ниже приводится реализация C ++ решения для динамического программирования.

C ++

#include<iostream>
#include<cstring>

using namespace std;

  
// Возвращает количество всех возможных круглых скобок, которые приводят к
// результат true для логического выражения с символами типа true
// и false и операторы типа &, | и ^ заполнены между символами

int countParenth(char symb[], char oper[], int n)

{

    int F[n][n], T[n][n];

  

    // Сначала заполняем диагональные записи

    // Все диагональные элементы в T [i] [i] равны 1, если символ [i]

    // это T (true). Аналогично, все записи F [i] [i] равны 1, если

    // символ [i] равен F (False)

    for (int i = 0; i < n; i++)

    {

        F[i][i] = (symb[i] == 'F')? 1: 0;

        T[i][i] = (symb[i] == 'T')? 1: 0;

    }

  

    // Теперь заполняем T [i] [i + 1], T [i] [i + 2], T [i] [i + 3] ... по порядку

    // И F [i] [i + 1], F [i] [i + 2], F [i] [i + 3] ... по порядку

    for (int gap=1; gap<n; ++gap)

    {

        for (int i=0, j=gap; j<n; ++i, ++j)

        {

            T[i][j] = F[i][j] = 0;

            for (int g=0; g<gap; g++)

            {

                // Найти место в скобках по текущему значению

                // разрыва

                int k = i + g;

  

                // Сохраняем Total [i] [k] и Total [k + 1] [j]

                int tik = T[i][k] + F[i][k];

                int tkj = T[k+1][j] + F[k+1][j];

  

                // Следуем рекурсивным формулам в соответствии с текущим

                // оператор

                if (oper[k] == '&')

                {

                    T[i][j] += T[i][k]*T[k+1][j];

                    F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]);

                }

                if (oper[k] == '|')

                {

                    F[i][j] += F[i][k]*F[k+1][j];

                    T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]);

                }

                if (oper[k] == '^')

                {

                    T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j];

                    F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j];

                }

            }

        }

    }

    return T[0][n-1];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char symbols[] = "TTFT";

    char operators[] = "|&^";

    int n = strlen(symbols);

  

    // Есть 4 способа

    // ((T | T) & (F ^ T)), (T | (T & (F ^ T))), (((T | T) & F) ^ T) и (T | ((T & F) ^ Т))

    cout << countParenth(symbols, operators, n);

    return 0;

}

Джава

class GFG 

{

      

    // Возвращает количество всех возможных

    // круглые скобки, которые приводят к

    // результат true для логического значения

    // выражение с символами вроде true

    // и false и операторы типа &, |

    // и ^ заполнены между символами

    static int countParenth(char symb[], 

                    char oper[], int n)    

    {

        int F[][] = new int[n][n];

        int T[][] = new int[n][n];

  

        // Сначала заполняем диагональные записи

        // Все диагональные записи в T [i] [i]

        // равны 1, если символ [i] равен T (true).

        // Аналогично, все записи F [i] [i]

        // равны 1, если символ [i] равен F (False)

        for (int i = 0; i < n; i++) 

        {

            F[i][i] = (symb[i] == 'F') ? 1 : 0;

            T[i][i] = (symb[i] == 'T') ? 1 : 0;

        }

  

        // Теперь заполняем T [i] [i + 1], T [i] [i + 2],

        // T [i] [i + 3] ... по порядку А F [i] [i + 1],

        // F [i] [i + 2], F [i] [i + 3] ... по порядку

        for (int gap = 1; gap < n; ++gap)

        {

            for (int i = 0, j = gap; j < n; ++i, ++j) 

            {

                T[i][j] = F[i][j] = 0;

                for (int g = 0; g < gap; g++) 

                {

                    // Найти место заключения в скобки

                    // используя текущее значение разрыва

                    int k = i + g;

  

                    // Сохраняем Total [i] [k] и Total [k + 1] [j]

                    int tik = T[i][k] + F[i][k];

                    int tkj = T[k + 1][j] + F[k + 1][j];

  

                    // Следуем рекурсивным формулам

                    // в соответствии с текущим оператором

                    if (oper[k] == '&'

                    {

                        T[i][j] += T[i][k] * T[k + 1][j];

                        F[i][j] += (tik * tkj - T[i][k] * T[k + 1][j]);

                    }

                    if (oper[k] == '|'

                    {

                        F[i][j] += F[i][k] * F[k + 1][j];

                        T[i][j] += (tik * tkj - F[i][k] * F[k + 1][j]);

                    }

                    if (oper[k] == '^')

                    {

                        T[i][j] += F[i][k] * T[k + 1][j] + 

                                    T[i][k] * F[k + 1][j];

                        F[i][j] += T[i][k] * T[k + 1][j] + 

                                    F[i][k] * F[k + 1][j];

                    }

                }

            }

        }

        return T[0][n - 1];

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        char symbols[] = "TTFT".toCharArray();

        char operators[] = "|&^".toCharArray();

        int n = symbols.length;

  

        // Есть 4 способа

        // ((T | T) & (F ^ T)), (T | (T & (F ^ T))),

        // ((((T | T) & F) ^ T) и (T | ((T & F) ^ T))

        System.out.println(countParenth(symbols,

                            operators, n));

    }

}

  
// Этот код был добавлен
// от 29AjayKumar

python3

# Возвращает количество всех возможных
# круглые скобки, которые приводят к
# результат true для логического значения
# выражение с символами вроде
# true и false и операторы
# как &, | и ^ заполнены между символами

def countParenth(symb, oper, n):

    F = [[0 for i in range(n + 1)] 

            for i in range(n + 1)]

    T = [[0 for i in range(n + 1)] 

            for i in range(n + 1)]

              

    # Сначала заполните диагональные записи

    # Все диагональные записи в

    # T [i] [i] равно 1, если символ [i]

    # - это T (правда). Точно так же все

    # F [i] [i] записей равны 1, если

    символом [i] является F (False)

    for i in range(n):

        if symb[i] == 'F':

            F[i][i] = 1

        else:

            F[i][i] = 0

  

        if symb[i] == 'T':

            T[i][i] = 1

        else:

            T[i][i] = 0

              

    # Теперь заполните T [i] [i + 1], T [i] [i + 2],

    # T [i] [i + 3] ... по порядку А

    # F [i] [i + 1], F [i] [i + 2],

    # F [i] [i + 3] ... по порядку

    for gap in range(1, n):

        i = 0

        for j in range(gap, n): 

            T[i][j] = F[i][j] = 0

            for g in range(gap):

                  

                # Найти место в скобках

                # используя текущее значение разрыва

                k = i + g

                  

                # Всего магазина [i] [k] и всего [k + 1] [j]

                tik = T[i][k] + F[i][k]; 

                tkj = T[k + 1][j] + F[k + 1][j];

                  

                # Следуйте рекурсивным формулам

                # в соответствии с текущим оператором

                if oper[k] == '&':

                    T[i][j] += T[i][k] * T[k + 1][j]

                    F[i][j] += (tik * tkj - T[i][k] * 

                                            T[k + 1][j])

                if oper[k] == '|':

                    F[i][j] += F[i][k] * F[k + 1][j]

                    T[i][j] += (tik * tkj - F[i][k] * 

                                            F[k + 1][j])

                if oper[k]=='^':

                    T[i][j] += (F[i][k] * T[k + 1][j] + 

                                T[i][k] * F[k + 1][j]) 

                    F[i][j] += (T[i][k] * T[k + 1][j] + 

                                F[i][k] * F[k + 1][j])

            i += 1

    return T[0][n - 1

      
Код водителя

symbols = "TTFT"

operators = "|&^"

n = len(symbols)

  
# Есть 4 способа
# ((T | T) & (F ^ T)), (T | (T & (F ^ T))),
# ((((T | T) & F) ^ T) и (T | ((T & F) ^ T))

print(countParenth(symbols, operators, n))

  
# Этот код предоставлен
# Сахил Шелангия

C #

// C # программа вышеуказанного подхода

using System;

  

class GFG 

{

      

    // Возвращает количество всех возможных

    // круглые скобки, которые приводят к

    // результат true для логического значения

    // выражение с символами вроде true

    // и false и операторы типа &, |

    // и ^ заполнены между символами

    static int countParenth(char []symb, 

                    char []oper, int n) 

    {

        int [,]F = new int[n, n];

        int [,]T = new int[n, n];

  

        // Сначала заполняем диагональные записи

        // Все диагональные записи в T [i, i]

        // равны 1, если символ [i] равен T (true).

        // Аналогично, все записи F [i, i]

        // равны 1, если символ [i] равен F (False)

        for (int i = 0; i < n; i++) 

        {

            F[i,i] = (symb[i] == 'F') ? 1 : 0;

            T[i,i] = (symb[i] == 'T') ? 1 : 0;

        }

  

        // Теперь заполняем T [i, i + 1], T [i, i + 2],

        // T [i, i + 3] ... по порядку А F [i, i + 1],

        // F [i, i + 2], F [i, i + 3] ... по порядку

        for (int gap = 1; gap < n; ++gap)

        {

            for (int i = 0, j = gap; j < n; ++i, ++j) 

            {

                T[i, j] = F[i, j] = 0;

                for (int g = 0; g < gap; g++) 

                {

                    // Найти место заключения в скобки

                    // используя текущее значение разрыва

                    int k = i + g;

  

                    // Сохраняем Total [i, k] и Total [k + 1, j]

                    int tik = T[i, k] + F[i, k];

                    int tkj = T[k + 1, j] + F[k + 1, j];

  

                    // Следуем рекурсивным формулам

                    // в соответствии с текущим оператором

                    if (oper[k] == '&'

                    {

                        T[i, j] += T[i, k] * T[k + 1, j];

                        F[i, j] += (tik * tkj - T[i, k] * T[k + 1, j]);

                    }

                    if (oper[k] == '|'

                    {

                        F[i,j] += F[i, k] * F[k + 1, j];

                        T[i,j] += (tik * tkj - F[i, k] * F[k + 1, j]);

                    }

                    if (oper[k] == '^')

                    {

                        T[i, j] += F[i, k] * T[k + 1, j] + 

                                    T[i, k] * F[k + 1, j];

                        F[i, j] += T[i, k] * T[k + 1, j] + 

                                    F[i, k] * F[k + 1, j];

                    }

                }

            }

        }

        return T[0,n - 1];

    }

  

    // Код драйвера

    public static void Main() 

    {

        char []symbols = "TTFT".ToCharArray();

        char []operators = "|&^".ToCharArray();

        int n = symbols.Length;

  

        // Есть 4 способа

        // ((T | T) & (F ^ T)), (T | (T & (F ^ T))),

        // ((((T | T) & F) ^ T) и (T | ((T & F) ^ T))

        Console.WriteLine(countParenth(symbols,

                            operators, n));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

4


Сложность времени:
O (n 3 )
Вспомогательное пространство: O (n 2 )

Ссылки:
http://people.cs.clemson.edu/~bcdean/dp_practice/dp_9.swf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проблема булевых скобок | DP-37

0.00 (0%) 0 votes