Короткое замыкание Префикс Булевы выражения

Question

У меня есть куча логических выражений, написанных в префиксной нотации (также называемой польской нотацией). Вложенные выражения в этом формате очень легко оценить (см. Алгоритм в статье Википедии).

Однако алгоритм, приведенный на странице Википедии, не допускает короткого замыкания (когда он оценивает and f() g()не пропускает оценку g() если f() ложно). Есть ли способ изменить алгоритм для включения короткого замыкания?

Answer 1

Вы можете использовать тот же алгоритм для построения дерева выражений: вместо оценки operand1 operator operand2создать узел с operand1 а также operand2 как дети, и operator как родитель.

Когда у вас есть дерево, вы можете оценить его (сверху вниз). Вы можете замкнуть оценку, не оценив одного из детей (например, если левый ребенок оценивает False и оператор and).

Вы заметите, что данный алгоритм эквивалентен оценке снизу вверх. Хотя это просто (и экономит память), вы не можете применить короткое замыкание, потому что вы никогда не знаете, должна ли даже оцениваться ветвь, в которой вы находитесь.

Answer 2

Я недавно должен был сделать это и придумал алгоритм, который, кажется, работает:

1. Разберите выражение, используя шунтирующий ярд, создав ряд постфиксов.

2. Найдите родительский оператор каждого члена и сохраните смещение.

   for term in terms:
       count = 0
       for next in remaining terms:
           if next type is function:
               count = count - (argument count - 1)
           else if next type is operator:
               count = count - 1
           else:
               count = count + 1
           if count is 0:
               next is term's parent
               offset = next - term
   

3. Оцените обычным способом и проверяйте наличие короткого замыкания после каждой операции. Переходите к сроку после родительского срока, если это применимо.

   for term in terms:
       if term is operator:
           pop 2 values
           evaluate (in reverse order)
           push result value
           if short-circuit (result is 0 and parent is AND, or result is non-zero and parent is OR):
               term = term + offset
       else if term is function:
           pop arguments
           evaluate (in reverse order)
           push result value
       else:
           push term value