Учитывая бинарную логическую формулу, как найти первичный/корневой оператор?

У меня есть двоичные логические функции в качестве входных строк, и мне нужен эффективный способ найти «основной» или «корневой» оператор. Некоторые ограничения на форму формулы заключаются в том, что есть только операторы «и» и «или» и нет отрицания. Входные строки обозначают операторы «и» как одиночные «а», а операторы «или» — как одиночные «о». Элементарные переменные представлены заглавными буквами. Я работаю в питоне. Например,

s = "( ( A o B ) a C ) a D" ==> корень = второй 'a'

s = "( A o B ) a ( C o D )" ==> root = 'a'

Вместо создания бинарного дерева для обхода я решил работать непосредственно с формулой для простоты в других областях программы. Кроме того, я хотел бы избежать необходимости создавать целое дерево для формулы, поскольку ее единственная цель - найти корень. Мне было интересно, есть ли у кого-нибудь эффективный способ найти корень?

Спасибо за вашу помощь!


python boolean logic
person stamps    schedule 22.02.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Учитывая корень, оба поддерева корня должны содержать сбалансированный набор скобок. Итак, если вы просто выполняете итерацию слева направо, пока не найдете первый оператор, когда скобки сбалансированы.

pcount = 0
for c in function_str:
    if c == '(': pcount += 1
    if c == ')': pcount -= 1
    if (c == 'a' or c == 'o') and pcount == 0: 
        return c # Root found

* Я не уверен на 100%, что это сработает во всех случаях, так как я подумал об этом только сейчас. Вы видите случаи, когда это не сработает?

person kefeizhou    schedule 22.02.2011
comment
Если круглые скобки сформированы минимально (т. е. без лишних наборов), это работает. Если у вас есть экстра, то есть s = (( A o B ) a ( C o D )), то это не удается. Может быть, вместо этого сохранить работающий наименьший найденный pcount, предполагая, что минимум должен быть равен 0? - person Hugh Bothwell; 22.02.2011

arrow_upward
0
arrow_downward

Как упоминалось выше Хью, эта модификация кода kefeizhou должна охватывать все случаи:

min_pcount, pcount = 10000, 0
root_node = '#'
for c in function_str:
    if c == '(': pcount += 1
    if c == ')': pcount -= 1
    if (c == 'a' or c == 'o'):
        if pcount < min_pcount:
            min_pcount = pcount
            root_node = c
return root_node
person lothario    schedule 22.02.2011