Kombinator ifadə
Kombinator məntiqini hesablama modellərindən biri kimi qəbul etmək olar. Bu model, kiçik sonlu bazisdən olan funksiyaların kompozisiyası vasitəsilə istənilən hesablana bilən funksiyanı ifadə etməyə imkan verir. Bu məsələdə biz BCKW bazisinin məhdud variantı olan BCKI-ni nəzərdən keçirəcəyik.
BCKI bazisindəki kombinator ifadə aşağıdakı qrammatikaya uyğun gələn bir sıra şəklindədir:
⟨Expression⟩ ::= ⟨Expression⟩ ⟨Term⟩ | ⟨Term⟩
⟨Term⟩ ::= ( ⟨Expression⟩ ) | B | C | K | I
Qrammatikadan göründüyü kimi, ifadə yarpaqlarında B, C, K və I olan kombinasiya ağacıdır. Kombinasiyalar sol assosiativdir. Məsələn, BIC ifadəsi (BI)C-yə ekvivalentdir, amma B(IC)-yə deyil.
İzahları asanlaşdırmaq üçün alt ifadələri təmsil etmək üçün böyük ingilis hərflərindən (a, ..., z) istifadə edəcəyik. Bu hərflər real məlumatlarda rast gəlinmir. Məsələn, BIC ifadəsini BxC (x = I), x (x = BIC), xy (x = BI, y = C), Bxy (x = I, y = C) kimi təqdim etmək olar, amma Bx kimi deyil.
pq ifadəsində p-ni q-ya tətbiq etdiyimizi deyəcəyik. Biz intuisiyamızı istifadə edərək p-ni funksiya və q-nu onun parametri kimi qəbul edə bilərik. Bununla belə, hesablama prosesi ənənəvi üsuldan xeyli fərqlənir - sabit ifadə ağacına dəyərlər ötürmək əvəzinə, həmin ağacı əvəz edərək hesablayırıq, buna görə nəticə müəyyən kombinator ifadədir.
İfadəni hesablamaq üçün aşağıdakı cədvəldə göstərilən şablonlardan birinə uyğun gələn bəzi alt ifadəni seçməliyik: yəni elə bir x (həmçinin ola bilsin y və z) olmalıdır ki, cədvəldən olan şablon alt ifadəyə bərabər olsun. Sonra alt ifadəni qısaltma ilə əvəz etmək lazımdır.
Əvəz etməni etdikdən sonra bu prosesi uyğun alt ifadə qalmayana qədər təkrarlamalıyıq. Bu son ifadə ilkin ifadənin normal formasıdır.
Məsələn, CIC(CB)I ifadəsində aşağıdakı hərf təyinatını edə bilərik
və görürük ki, CIC(CB)I = (((CI)C)(CB))I = (((Cx)y)z)I ifadəsi C - kombinasiya ehtiva edir və buna görə ((xz)y)I = I(CB)CI-yə qısaldılır:
Başqa bir ifadə nümunəsi: B((CK)I)IC. B kombinasiya qısaldılır:
İndi son I qısaldılır:
Və hesablama iki qısaltma ilə tamamlanır:
Göstərmək olar ki, normal forma qısaltmaların ardıcıllığından asılı olmayaraq eyni qalır. Məsələn, aşağıdakı hesablama ardıcıllığı
eyni nəticəyə gətirib çıxarır ki,
Lakin gördüyünüz kimi, qısaltmaların sayı fərqlidir: birinci halda 3, ikinci halda 2. Qarşımızda maraqlı bir vəzifə durur - verilmiş formul üçün minimum qısaltma sayı ilə hesablama ardıcıllığını tapmaq.
Verilmiş kombinator ifadəni normal formaya çevirmək üçün lazım olan minimum qısaltma sayını tapacaq bir proqram yazın.
Giriş məlumatları
Yeganə sıra yuxarıda göstərilən qrammatikaya uyğun gələn kombinator ifadəni ehtiva edir. İfadənin uzunluğu 30000-dən çox deyil. İfadə qrammatikada göstərilməyən boşluqlar və ya simvollar ehtiva etmir.
Çıxış məlumatları
Verilmiş formulu normal formaya gətirmək üçün lazım olan minimum çevrilmə sayını çıxarın.