Term Generator

Bir formulun sintaksisi şəkildə 1(a) göstərildiyi kimidir. Əgər bir formul şəkildə 1(b) verilən xüsusi sintaksisə malikdirsə, biz deyirik ki, formul Normal Formadadır (NF).

Bir formul aşağıda verilmiş yenidən yazma qaydalarına uyğun olaraq NF-ə çevrilir. Burada F formulunu, S formulaların boş olmayan ardıcıllığını, s və s' isə ehtimal ki, boş olan formulaların ardıcıllığını təmsil edir. Bir formul F-də q → r yenidən yazma qaydasını tətbiq etmək, F-in q nümunəsinə uyğun olan bir hissəsini r ilə əvəz etmək deməkdir, şəkildə 2-də göstərildiyi kimi. Çevrilmə heç bir yenidən yazma qaydası tətbiq edilə bilmədikdə başa çatır. Çevrilmə hər hansı bir formul üçün başa çatır və nəticə unikaldır, hansı qaydaların formulun hansı hissələrinə və hansı ardıcıllıqla tətbiq edilməsindən asılı olmayaraq.

1. (+F) → F

2. (*F) → F

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

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

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

Qoy NF(F) formulunun F normal forması olsun. Problem, verilmiş formul F və bir ədəd k üçün NF(F)-dən ardıcıl k terminləri NF(F)-də göründüyü ardıcıllıqla çıxaran bir termin generatoru yazmaqdır. Əgər terminlər tükənərsə, generator NF(F)-in ilk terminindən davam edir. Məsələn, F=(+(*(+(*ab)(+a))b)) və NF(F)=(+(*abb)(*ab)) şəkildə 2-də olduğu kimi. NF(F)-dən ilk termini yaratmaq (*abb) verir. İki daha termin yaratmaq (*ab), (*abb) verir. Qeyd edək ki, əgər NF(F) oxşar terminlər ehtiva edirsə, son nümunədə olduğu kimi, bu terminlər fərqli hesab olunur.

Giriş verilənləri

Standart girişdən məlumat dəstlərini oxuyan bir termin generatoru yazın. Məlumat dəstinin məzmunu F k_1 ... k_N 0, n > 0, burada F formul, və k_1 ... k_N 0-dan fərqli uzun tam ədədlərdir.

Hər çap olunan termin bir sətirin əvvəlindən başlayır və termin simvolları arasında boşluqlar yoxdur. Əgər k_i < 0 olarsa, yaradılan terminlər çap olunmur. Girişdə boşluqlar sərbəst istifadə olunur. Girişdəki hər bir formul F ən çox 150 simvola malikdir və NF(F)-in hər bir termini ən çox 80 simvol uzunluğundadır, boşluqlar nəzərə alınmadan. Giriş məlumatları faylın sonu ilə bitir və düzgündür.

Çıxış verilənləri

Hər bir k_i üçün, i = 1, n, proqram NF(F)-dən ardıcıl |k_i| terminlərini yaradır və əgər k_i > 0 olarsa, bu terminləri standart çıxışda çap edir.