Комбінаторний вираз
Комбінаторну логіку можна розглядати як одну з обчислювальних моделей, що дозволяє виразити будь-яку обчислювану функцію у вигляді композиції функцій з невеликого кінцевого базису. У цій задачі ми розглянемо обмежений варіант базису 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 у другому. Перед нами з'являється цікаве завдання - знайти порядок обчислень з мінімальною кількістю скорочень для даної формули.
Напишіть програму, яка знайде мінімальну кількість скорочень, необхідну для перетворення заданого комбінаторного виразу в нормальну форму.
Вхідні дані
Єдиний рядок містить комбінаторний вираз, що відповідає вищенаведеній граматиці. Довжина виразу не перевищує 30000. Вираз не містить пробілів або символів, не вказаних у граматиці.
Вихідні дані
Виведіть мінімальну кількість перетворень, необхідних для зведення заданої формули до нормальної форми.