Дано логическое выражение со следующими символами.
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>
usingnamespacestd;
// Возвращает количество всех возможных круглых скобок, которые приводят к // результат true для логического выражения с символами типа true // и false и операторы типа &, | и ^ заполнены между символами
intcountParenth(charsymb[], charoper[], intn)
{
intF[n][n], T[n][n];
// Сначала заполняем диагональные записи
// Все диагональные элементы в T [i] [i] равны 1, если символ [i]
// это T (true). Аналогично, все записи F [i] [i] равны 1, если
// символ [i] равен F (False)
for(inti = 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(intgap=1; gap<n; ++gap)
{
for(inti=0, j=gap; j<n; ++i, ++j)
{
T[i][j] = F[i][j] = 0;
for(intg=0; g<gap; g++)
{
// Найти место в скобках по текущему значению
// разрыва
intk = i + g;
// Сохраняем Total [i] [k] и Total [k + 1] [j]
inttik = T[i][k] + F[i][k];
inttkj = 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];
}
}
}
}
returnT[0][n-1];
}
// Программа драйвера для проверки вышеуказанной функции
# Возвращает количество всех возможных # круглые скобки, которые приводят к # результат true для логического значения # выражение с символами вроде # true и false и операторы # как &, | и ^ заполнены между символами