Комбінаторний вираз

Комбінаторну логіку можна розглядати як одну з обчислювальних моделей, що дозволяє виразити будь-яку обчислювану функцію у вигляді композиції функцій з невеликого кінцевого базису. У цій задачі ми розглянемо обмежений варіант базису BCKW, а саме BCKI.

Комбінаторний вираз у BCKI базисі є рядком, що відповідає наступній граматиці:

⟨Expression⟩ ::= ⟨Expression⟩ ⟨Term⟩ | ⟨Term⟩

⟨Term⟩ ::= ( ⟨Expression⟩ ) | B | C | K | I

Як видно з граматики, вираз являє собою дерево комбінацій, у листках якого знаходяться B, C, K і I. Комбінації є лівоасоціативними. Наприклад, BIC еквівалентно (BI)C, але не B(IC).

Для зручності пояснень будемо використовувати прописні англійські букви (a, ..., z) для представлення підвиразів. Ці букви не зустрічаються в реальних даних. Наприклад, BIC можна представити у вигляді BxC (x = I), x (x = BIC), xy (x = BI, y = C), Bxy (x = I, y = C), але ніяк Bx.

Будемо говорити, що у виразі pq ми застосовуємо p на q. Ми можемо використовувати нашу інтуїцію, кажучи, що p функція, а q її параметр. Тим не менш, процес обчислення досить сильно відрізняється від традиційного - замість передачі значень фіксованому дереву виразів, ми обчислюємо, замінюючи це саме дерево, тому результатом є деякий комбінаторний вираз.

Для обчислення виразу нам потрібно вибрати деякий підвираз, що відповідає одному з вказаних у таблиці нижче шаблонів: тобто має існувати таке x (а також можливо y і z), що шаблон з таблиці стає рівним підвиразу. Потім слід замінити підвираз на скорочення.

Після здійснення заміни ми повинні повторювати цей процес, поки не залишиться жодного підходящого підвиразу. Це остаточний вираз і є нормальною формою вихідного.

Наприклад, у виразі CIC(CB)I ми можемо здійснити таке присвоєння літералів

і побачити, що CIC(CB)I = (((CI)C)(CB))I = (((Cx)y)z)I містить C - комбінацію і тому зводиться до ((xz)y)I = I(CB)CI:

Ще один приклад виразу: B((CK)I)IC. Редукуємо комбінацію B:

Тепер редукуємо останнє I:

І завершуємо обчислення ще двома редукціями:

Можна показати, що нормальна форма залишається тією ж самою незалежно від порядку редукцій. Наприклад, наступний порядок обчислень

веде до того ж результату, що і

Однак, як Ви бачите, кількість скорочень відрізняється: $3$ у першому випадку і $2$ у другому. Перед нами з'являється цікаве завдання - знайти порядок обчислень з мінімальною кількістю скорочень для даної формули.

Напишіть програму, яка знайде мінімальну кількість скорочень, необхідну для перетворення заданого комбінаторного виразу в нормальну форму.