Генератор термінів

Формула має синтаксис, показаний на рисунку 1(a). Якщо формула відповідає конкретному синтаксису, наведеному на рисунку 1(b), ми кажемо, що формула знаходиться в Нормальній Формі (NF).

Формула перетворюється в NF згідно з правилами переписування, наведеними нижче, де F представляє формулу, S означає непорожню послідовність формул, а s та s' позначають, можливо, порожні послідовності формул. Застосування правила переписування q → r до формули F означає заміну частини F, що відповідає шаблону q, на r, як показано на рисунку 2. Перетворення завершується, коли жодне правило переписування не може бути застосоване. Перетворення завершується для будь-якої формули, і результат є унікальним незалежно від того, які правила застосовуються до яких частин формули і в якому порядку.

1. (+F) → F

2. (*F) → F

3. (+s(+S)s') → (+sSs')

4. (*s(*S)s') → (*sSs')

5. (*s(+FS)s') → (+(*sFs')(*s(+S)s'))

Нехай NF(F) є нормальною формою формули F. Завдання полягає в тому, щоб написати генератор термів, який для заданої формули F і числа k виводить наступні k термів з NF(F) в порядку, в якому вони з'являються в NF(F). Якщо терми вичерпуються, генератор продовжує з першого терма NF(F). Наприклад, розглянемо F=(+(*(+(*ab)(+a))b)), і NF(F)=(+(*abb)(*ab)) як на рисунку 2. Генерація першого терма з NF(F) дає (*abb). Генерація ще двох термів дає (*ab), (*abb). Зверніть увагу, що якщо NF(F) містить схожі терми, як у останньому прикладі у вхідних/вихідних даних, ці терми вважаються різними.

Вхідні дані

Напишіть генератор термів, який зчитує набори даних зі стандартного вводу. Вміст набору даних — це F k_1 ... k_N 0, n > 0, де F — це формула, а k_1 ... k_N — довгі цілі числа, відмінні від 0.

Кожен надрукований терм починається з початку рядка, і між символами терма немає пробілів. Згенеровані терми не друкуються, якщо k_i < 0. Пробіли вхідних даних використовуються вільно. Кожна формула F у вхідних даних має не більше 150 символів, і кожен терм з NF(F) має не більше 80 символів, не враховуючи пробілів. Вхідні дані завершуються кінцем файлу і є коректними.

Вихідні дані

Для кожного k_i, i = 1, n, програма генерує наступні |k_i| терми з NF(F) і, якщо k_i > 0, друкує ці терми на стандартний вихід.