Число маршрутов во фрагментах, содержащих булевы операции

Ранее рассмотренные в примерах фрагменты содержали конструкции логического или множественного выбора, в условных вершинах которых содержались элементарные логические условия без знаков булевых операций “И” и “ИЛИ”. Поэтому число путей фрагмента определялось визуально без дополнительных построений. Однако наличие знаков булевых операций в логических выражениях требует построения специальной схемы для расчета числа путей как для единичного значения выражения так и для нулевого. В качестве такой схемы предлагается использовать линейный бинарный граф [4] (ЛБГ). Построение ЛБГ и расчет числа путей, порождаемых логическим выражением с булевыми операциями, рассмотрим на следующем примере.

Пусть в условной вершине некоторого фрагмента представлено сложное логическое выражение вида

( Sin(a) == Cos(b) && (! c % 5 || d > 3) && (e <= exp(f) || func(g)) ).

Здесь указаны: операции сравнения (“==“, “>“, “<=“), деления по модулю (“%”), булевы операции (“!” - инверсия, “&&” - И, “||” - ИЛИ), функции синуса, косинуса, экспоненты и некоторой целочисленной функции (func). Введем понятие “атом” - это подформула, ограниченная слева и справа знаками булевых операций. В данном случае атомами являются следующие подформулы: Sin(a) == Cos(b), c % 5, d > 3, e <= exp(f), func(g).

Если в формуле содержится знак инверсии перед заключенной в скобки булевой операцией, то знак этой операции изменяется (И на ИЛИ и наоборот), а знак инверсии исключается перед данной подформулой и ставится перед каждым членом замененной операции. В данной формуле этого не требуется.

Для построения ЛБГ разместим атомы друг под другом в порядке обхода всей формулы слева направо (рис. 6) и соединим их дугами, направленными вниз. Атомы образуют вершины ЛБГ, а дуги - связь между соседними вершинами. Вслед за последним (нижним) атомом разместим две вершины, соответствующие результатам вычисления формулы - единичному и нулевому; нижний атом соединим дугами с указанными новыми вершинами. Все ранее построенные дуги называются основными дугами ЛБГ. Теперь построим дуги, называемые переходами.

Рис.6. ЛБГ и расчет числа его нулевых и единичных путей.

Переходы строятся по обе стороны от оси ЛБГ, образуемой основными дугами между вершинами - атомами. Переходы строятся начиная с вершины, предшествующей последнему атому (в нашем случае с вершины “e <= exp(f)”). Переход строится на той стороне от оси, где расположена вершина “результат 1”, если в формуле справа от соответствующего атома стоит знак ИЛИ. В примере это переходы от атомов “e <= exp(f)” и “!c%5”.Переход строится на другой стороне от оси, если в формуле справа от атома стоит знак И. Это переходы от атомов “d > 3” и “Sin(a) == Cos(b)”. Переход направляется к расположенной на стороне его построения вершине “результат 1(0)”, если упомянутый знак ИЛИ (И) принадлежит внешней операции формулы. Это переходы от атомов “Sin(a) == Cos(b)” и “d > 3”. В противном случае переход направляется к ниже расположенной вершине, соответствующей атому, размещенному справа от закрывающей скобки, ограничивающей операцию,которой принадлежит упомянутый знак ИЛИ (И), а если такого атома нет - к вершине “результат”. Это переходы от атомов “! c % 5” и “e <= exp(f)”. Знак булевой операции отрицания на расчет числа путей не влияет, поэтому в построенном, следуя вышесказанному, ЛБГ он игнорируется (см. рис. 6). Формальное описание синтеза ЛБГ представлено в [5]. Теперь рассмотрим процесс подсчета числа единичных и нулевых путей в построенном ЛБГ. Будем использовать специальную метку, представляющую собой два числа, разделенную знаком дроби. При этом левое число будет обозначать число нулевых путей, а правое - единичных. Например, метка “3 / 5” показывает три нулевых и пять единичных путей.

Логично предположить, что расчет числа путей надо начинать от начальной вершины. Но предлагается более простой алгоритм подсчета, начиная с вершин “результат”. Под вершиной “результат 0” поставим метку “1 / 0”, а под вершиной “результат 1” - метку “0 / 1”. На каждой дуге, заходящей в вершину “результат” поставим такую же соответствующую метку. Далее, для каждой вершины ЛБГ, начиная с последнего атома и следуя вверх, выполнить следующее. Сложить метки “a0 / a1” и “b0 / b1”, указанные на исходящих из данной вершины дугах, в результате чего получится метка “c0 / c1”, где c0 = a0 + b0, c1 = a1 + b1. Полученную метку поставить на каждой заходящей в данную вершину дуге. В результате над самой верхней вершиной ЛБГ получается метка “s0 / s1”, где s0 - число нулевых путей, то есть число путей, определяющих результат 0, а s1 - число единичных путей, определяющих результат 1.