task.md

Полином Жегалкина

Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 1 с
Ограничение по памяти: 256 МБ

Определим рекуррентно понятие формулы булевой функции:

1. 0 и 1 — формулы.
2. Если x — переменная, то x — формула.
3. Если A и B — формулы, то ( A op B ) — формула, где op — одна из допустимых бинарных операций.
4. Если A — формула, то ( op A ) — формула, где op — одна из допустимых унарных операций.
5. Других формул нет.

Допустимы следующие унарные операции:

• ~ — отрицание.

Допустимы следующие бинарные операции:

• / — дизъюнкция;
• /\ — конъюнкция;
• -> — импликация;
• <=> — эквивалентность;
• ^ — сумма по модулю 2;
• | — штрих Шеффера;
• ! — стрелка Пирса.

Формат входных данных:

В единственной строке записана булева функция. Имена переменных имеют вид x_i (i — натуральное число). Будем считать, что количество переменных функции равно наибольшему номеру переменной в формуле. Если переменных в формуле нет, то функция является константой. Пусть d — глубина дерева операций, представляющего формулу, а n — число переменных функции. Тогда гарантируется, что d + n ≤ 24 Словом будем называть либо скобку, либо переменную, либо операцию. Все слова разделены одним пробелом. Общий размер файла не превосходит 2²² байт.

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

Выведите в единственной строке вектор коэффициентов полинома Жегалкина для данной булевой функции без разделителей, состоящий из 0 и 1. Каждый символ является коэффициентом при наборе значений, соответствующем строке таблицы истинности, строки которой расположены в лексикографическом порядке, а столбцы — в порядке возрастания индексов переменных.

Примеры

input.txt	output.txt
1	1
x1	01
( x1 /\ x2)	0001

Решение