T. Таблицы истинности 3

Продолжим работу с таблицами истинности.
К сожалению, некоторые из операций Булевой алгебры не реализованы в Python.
Самые частые не стандартные операции это: импликация, строгая дизъюнкция и эквивалентность.

Обозначим их следующим образом:

• импликация — ->;
• строгая дизъюнкция — ^;
• эквивалентность — ~.

Напишите программу, которая для введённого сложного логического высказывания строит таблицу истинности.

Формат ввода

Вводится логическое выражение от нескольких переменных.

Возможное содержание выражения:

• Заглавная латинская буква — переменная;
• not — отрицание;
• and — конъюнкция;
• or — дизъюнкция;
• ^ — строгая дизъюнкция;
• -> — импликация;
• ~ — эквивалентность;
• () — логические скобки.

Формат вывода

Выведите таблицу истинности данного выражения.

Примечание

Прежде, чем реализовывать новые операции, обратите внимание на их приоритет.
Рекомендуем воспользоваться знаниями полученными при решении задачи «Польский калькулятор».

Пример

Ввод

A -> B ~ C

Вывод

A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1

Ввод

A or C ~ not (A -> B) or C

Вывод

A B C F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1

Решение

Развитие предыдущей задачи. Одна из самых сложных задач курса.
Авторы немного лукавят, говоря о том, что в python не реализована часть функций, так например, с точки зрения этой задачи, строгая дизьюнкция (^) – это оператор !=, импликация (->) – оператор <=, эквивалентность (~) – ==.

Кажется, что можно просто заменить все “неправильные” операторы на правильные и пусть python дальше сам разбирается что и как считать. И при таком подходе даже пройдет первый тест, но уже на втором нас ждет разочарование. Функция eval() будет аловаться на неправильный синтаксис записи A or C == not (A <= B) or C. Все дело в том, что правильная интерпретация должна выглядеть как (A or C) == (not (A <= B) or C).

А это значит, что нам или надо научиться расставлять скобки, или “есть слона по частям” и воспользоваться знаниями из задачи T. Польский калькулятор — 2 для разбора выражения на части с учетом приоритетов и вычисления этих частей с помощью функции eval().

from itertools import product

OPERATORS = {
    'not': 'not',
    'and': 'and',
    'or': 'or',
    '^': '!=',
    '->': '<=',
    '~': '==',
}

PRIORITY = {
    'not': 0,
    'and': 1,
    'or': 2,
    '^': 3,
    '->': 4,
    '~': 5,
    '(': 6,
}


def parse_expression(expression, variables):
    stack = []
    result = []

    expression = expression.replace('(', '( ').replace(')', ' )')

    for item in expression.split():
        if item in variables:
            result.append(item)
        elif item == '(':
            stack.append(item)
        elif item == ')':
            while stack[-1] != '(':
                result.append(OPERATORS[stack.pop()])
            stack.pop()
        elif item in OPERATORS:
            while stack and PRIORITY[item] >= PRIORITY[stack[-1]]:
                result.append(OPERATORS[stack.pop()])
            stack.append(item)
    while stack:
        result.append(OPERATORS[stack.pop()])
    return result


def evaluate(expression, variables):
    stack = []
    for item in expression:
        if item in variables:
            stack.append(variables[item])
        else:
            if item == 'not':
                stack.append(not stack.pop())
            else:
                variable2, variable1 = stack.pop(), stack.pop()
                stack.append(eval(f'{variable1} {item} {variable2}'))  # noqa
    return int(stack.pop())


expression = input()
variables = sorted(set([item for item in expression if item.isupper()]))
parsed_expression = parse_expression(expression, variables)
table = product([0, 1], repeat=len(variables))

print(*variables, 'F')
for values in table:
    globals = {key: value for key, value in zip(variables, values)}
    print(*values, evaluate(parsed_expression, globals))