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

Question

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

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

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

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

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

Answer 1

Для данного корня оба поддерева корня должны содержать сбалансированный набор скобок. Так что, если вы просто итерируете слева направо, пока не найдете первый оператор, когда скобки сбалансированы.

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%, что это будет работать во всех случаях, так как я думал об этом только сейчас. Вы видите случаи, когда это не сработает?

Answer 2

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

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