Продолжим работу с таблицами истинности.
К сожалению, некоторые из операций Булевой алгебры не реализованы в 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))
забавно как до этого в заданиях всё было топорно, теперь раз мы познакомились со списочными выражениями, теперь можно применять их в полную мощь
хочу позже самостоятельно написать код без списочных выражений
сложно привыкнуть к
*[v for v in variables]
долго думал как использовать a,b,c да ещё и регулировать количество переменных
не смог понять подсказку с символами верхнего регистра
воспользовался str.lower()
не секрет почему globals??
понять различие думаю проще в рамках более сложного кода??
про eval читал отсюда
https://docs-python.ru/tutorial/opredelenie-funktsij-python/oblast-vidimosti-peremennyh/
В этом задании наши переменные только заглавные буквы, а операторы написаны строчными. соотвественно самый простой способ их разделить – по регистру. Но если ввести a AND b то код сломается. Это не сильно большая проблема, потому что всегда можно переделать ту часть, которая отвечает за “добывание” переменных. Можно, например, искать все односимвользые имена, а можно считать переменными любые слова, не совпадающие с разрешенными операторами.
Global потому что если делать local, то придется писать пустой словарь. В нашем задании разницы нет никакой. Но в реальном программировании разница между ними в том, что global могут измениться в процессе выполнения eval, а local – нет. Первые разделены между основным кодом и eval, а вторые существуют только внутри eval.
1)
Можно, например, искать все односимвольные имена, а можно считать переменными любые слова, не совпадающие с разрешенными операторами.
круто))
2)
то есть, если данный код существует внутри большой программы, то верно будет использовать locals.
И использование locals будет по другому?
Locals почти всегда будет лучше и безопаснее чем globals.
Вызов будет выглядеть примерно так:
eval(expression, {}, locals))1)parse_expression относится к какому либо алгоритму??
while stack and PRIORITY[item] >= PRIORITY[stack[-1]]:
2)почему если второго значения нету(значение stack не существует в PRIORITY)
то условие не проходит ???
def evaluate(expression, variables):
stack = []
3) stack может остаться не пустым после parse_expression???
4)можно попросить объяснение правильности вычисления?
я вижу что каким то образом после parse_expression мы получаем упорядоченный список, но не могу понять, как это работает.
это алгоритм??
например такое выражение, код правильно посчитает??
not A or (C ~ not (A -> B) or C)
мой код считает только для одной пары скобочек
def truth_tables(tokens):
# tokens = input()
lst_tokens = tokens.split()
variables = [v for v in sorted(set(list(tokens))) if v.isupper()]
print(*[v for v in variables], ‘F’)
length = len(variables)
def br(tokens):
if ‘(‘ in list(tokens):
brackets = tokens[tokens.index(‘(‘):tokens.index(‘)’) + 1].strip(‘()’).split()
brackets = translator(brackets)
res_lst_tokens = tokens[:tokens.index(‘(‘)].split()
res_lst_tokens.append(brackets)
res_lst_tokens.extend(tokens[tokens.index(‘)’) + 1:].split())
lst_tokens = res_lst_tokens
def translator(expression):
operators = [‘not’, ‘and’, ‘or’, ‘^’, ‘->’, ‘~’]
for operation in operators:
if operation in expression:
match operation:
case ‘not’:
for _ in range(expression.count(operation)):
index = expression.index(operation)
bracket = ‘(‘ + expression.pop(index) + ‘ ‘ + expression.pop(index) + ‘)’
expression.insert(index, bracket)
case ‘and’ | ‘or’:
for _ in range(expression.count(operation)):
index = expression.index(operation)
bracket = ‘(‘ + expression.pop(index – 1) + ‘ ‘ + expression.pop(
index – 1) + ‘ ‘ + expression.pop(index – 1) + ‘)’
expression.insert(index – 1, bracket)
case ‘^’:
index = expression.index(operation)
a = expression.pop(index – 1)
expression.pop(index – 1)
b = expression.pop(index – 1)
strict_disjunction = ”.join([‘(not ‘ + a + ‘ and ‘ + b + ‘ or ‘ + a + ‘ and ‘ + ‘ not ‘, b, ‘)’])
expression.insert(index – 1, strict_disjunction)
case ‘->’:
index = expression.index(operation)
a = expression.pop(index – 1)
expression.pop(index – 1)
b = expression.pop(index – 1)
impl = ”.join([‘(‘, ‘not ‘, a, ‘ or ‘, b, ‘)’])
expression.insert(index – 1, impl)
case ‘~’:
index = expression.index(operation)
a = expression.pop(index – 1)
expression.pop(index – 1)
b = expression.pop(index – 1)
equ = ”.join([‘(not ‘ + a + ‘ and ‘ + ‘ not ‘ + b + ‘ or ‘ + a + ‘ and ‘ + b + ‘)’])
expression.insert(index – 1, equ)
res = ”
for _ in expression:
res += _
return res
if ‘(‘ in list(tokens):
brackets = tokens[tokens.index(‘(‘):tokens.index(‘)’) + 1].strip(‘()’).split()
brackets = translator(brackets)
res_lst_tokens = tokens[:tokens.index(‘(‘)].split()
res_lst_tokens.append(brackets)
res_lst_tokens.extend(tokens[tokens.index(‘)’) + 1:].split())
lst_tokens = res_lst_tokens
to_eval = translator(lst_tokens)
for val in product([False, True], repeat=length):
d = {k: int(v) for k, v in zip(variables, val)}
print(*[v for v in d.values()], int(eval(to_eval, d)))
def main():
string = input()
truth_tables(string)
if __name__ == ‘__main__’:
main()
# not A or (C ~ not (A -> B) or C)
1. Это этап подготовки данных. На нем мы токенезируем скобочки для более простого распознавания и закладываем данные в стек согласно приоритету операций.
2. В пайтоне ленивые вычисления, поэтому если первое значение в логическом выражении содержащем AND возвращает False дальнейшие вычисления не ведутся. Подробнее о сравнении о том почему сама по себе переменная уже может быть признаком True или False можно прочитать тут – Проверка на пустоту
3. Да, если выражение содержит ошибки и не может быть распарсено.
4. Это называется стек. Смысл его в том, чтобы переменные попадающие в него возвращались в обратном порядке. Этот прием в программировании сложных процессов используется очень и очень часто, поэтому стоит изучить его повнимательнее. Когда дойдете до раздела ООП, то там будет задание на реализацию стека. На пайтоне реализовать стек очень просто, но в других языках программирования это бывает не сильно тривиальной задачей.
Когда мне надо проверить чей-то код, я создаю файл у себя в VS Code и проверяю на данных, результат для которых у меня есть. Или на случайных, если у меня есть программа – эталон. Иногда бывает интересно отладить его, чтобы понять как он работает, если сразу не очевидно.
1, 4)
переночевал с моими вопросами в голове. понял что ответ на мой вопрос будет – стек. но я не это имел в виду. я имею в виду ….. каким образом можно прийти к этому? Опыт?
я вижу что у вас есть условие при котором мы вносим упорядочено значения из скобок
я вижу что у вас есть условие при котором в зависимости от приоритета операции вы вносите упорядочено значения
я вижу что вы можете полностью все операторы добавить в result
после этого вы пользуетесь, в своё время нашумевшим, польским калькулятором
просто я не понимаю, как к этому прийти
как написать эти условия??)))
возможно это очевидно, но ведь как-то эту очевидность нужно внести в программу
2) спасибо за ссылку и за знания))
4)
Теперь начинаю жалеть что не сам решил эту задачу, а подглядел по итогу ваше решение, хотя думаю я бы не осилил его в адекватные сроки.
https://leetcode.com/tag/stack/
полагаю у меня ещё есть возможность потренироваться))
Может быть вы подскажите другие ресурсы??
Это все конечно приходит с опытом. Когда я только начинал изучать программирование по-настоящему, я бы тоже не осилил такое решение. Стек и очереди в пайтоне очень просты в реализации, поэтому стоит изучать эти понятия как раз в этом языке, чтобы сконцентрироваться на сути происходящего, а не на реализации процессов. Потом, когда почувствуете, сможете их правильно применять. Но даже сейчас для меня иногда не сразу очевидно что стоит идти через стек для решения той или иной задачи.
Чаще всего стек нужен там, где можно отложить принятие решения для того чтобы заглянуть что там дальше в данных.
leetcode хороший ресурс. Можно еще codewars попробовать.
#вариант решения без стека, тесты проходит отлично:
from itertools import product
text = input().replace(‘(‘, ‘( ‘).replace(‘)’, ‘ )’)
param = [word for word in sorted(set(text.split())) if word.isupper()]
count = len(param)
text = text.replace(‘( ‘, ‘((((‘).replace(‘ )’, ‘))))’)
text = “(((” + “))) == (((“.join(text.split(‘~’)) + “)))”
text = “((” + “)) <= ((“.join(text.split(‘->’)) + “))”
text = “(” + “) != (“.join(text.split(‘^’)) + “)”
print(” “.join(param), ‘F’)
for vars in product([0, 1], repeat=count):
dic = {k: v for (k, v) in zip(param, vars)}
print(” “.join([str(var) for var in vars]), int(eval(text, dic)))
from itertools import product
text = input().replace(‘(‘, ‘( ‘).replace(‘)’, ‘ )’)
param = [word for word in sorted(set(text.split())) if word.isupper()]
count = len(param)
text = text.replace(‘( ‘, ‘((((‘).replace(‘ )’, ‘))))’)
text = “(((” + text.replace(‘~’, “))) == (((“) + “)))”
text = “((” + text.replace(‘->’, “)) <= ((“) + “))”
text = “(” + text.replace(‘^’, “) != (“) + “)”
print(” “.join(param), ‘F’)
for vars in product([0, 1], repeat=count):
dic = {k: v for (k, v) in zip(param, vars)}
print(” “.join([str(var) for var in vars]), int(eval(text, dic)))
Наверное был бы хороший вариант, если бы не засилие скобочек делающих замены нечитаемыми. Мне кажется, стоило использовать f-строки для большей читабельности.
text = f"({text.replace('^', ') != (')})"Что-то типа такого.
а еще лучше
not_eq = ') != (' text = f"({text.replace('^', not_eq)})"Ну и слегка читерский подход. Это примерно как решать задачу про “распрямление” вложенных списков с помощью замены квадратных скобочек на запятую.
Тем не менее, задача решена и решена довольно эффективно.
согласен читабельность пока у меня хромает, борюсь)
Хотел просто показать принцип, что сделать замену скобок возле операторов в зависимости от приоритета, причем начальные скобки заменить на самое большое число скобок, можно этот момент закодить не прописывая скобки самому, а беря приоритет из словаря как у вас в решении + еще по хорошему сделать пробежку и почистить лишние скобки(но решил что для этой задачи избыточное украшательство).
В любом случае на это решение меня натолкнуло ваше объяснение проблематики приоритетов, за что опять таки сердечно благодарю!)