Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1233. NOT
Лексический анализГрамматики, рекурсивный разбор
Олимпиадные задачи на русском языке
| 26/04/2009 | Очный тур олимпиады для школьников Информатика-2009 (4) |
| 15/04/2013 | Занятие 24 (D) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Логические выражения, содержащие отрицания, трудны для понимания, поэтому программисты, особенно начинающие, должны их избегать. Напишите программу, которая выполняет рефакторинг логического выражения на языке Паскаль, преобразуя его к виду, не содержащему операции NOT, используя правила де Моргана, удаление двойного отрицания и замену операций отношения на инверсные.
Логическое выражение в этой задаче имеет следующий синтаксис:
выр ::= выр1 | выр4
выр1 ::= выр2 | выр1 «OR» выр2
выр2 ::= выр3 | выр2 «AND» выр3
выр3 ::= «(» выр «)» | «NOT» выр3
выр4 ::= идент «=» идент | идент «<>» идент | идент «>» идент | идент «<» идент | идент «>=» идент | идент «<=» идент
идент ::= «A» | «B» | … | «Z»
Для удаления отрицания используются следующие правила:
NOT(A OR B) `→` NOT(A) AND NOT(B)
NOT(A AND B) `→` NOT(A) OR NOT(B)
NOT(NOT A) `→` A
NOT(A<B) `→` A>=B
NOT(A>B) `→` A<=B
NOT(A<=B) `→` A>B
NOT(A>=B) `→` A<B
NOT(A=B) `→` A<>B
NOT(A<>B) `→` A=B
Формат ввода
В первой строке ввода логическое выражение, соответствующее указанному синтаксису. Между лексемами могут быть пробелы. Длина строки не превышает 200 символов. Строчные буквы в записи выражений не используются.
Формат вывода
Вывести логическое выражение после удаления отрицаний. Других преобразований в логическом выражении кроме вышеуказанных делать нельзя. Скобки должны использоваться только там, где они необходимы для указания порядка выполнения операций. Самый низкий приоритет в языке Паскаль у операций сравнения, выше у операции OR, еще выше у операции AND. Пробелы в выходном логическом выражении должны отсутствовать.
Пример ввода
NOT((A>=B) OR (C<X) AND (D<>X))
Пример вывода
(A<B)AND((C>=X)OR(D=X))
