Комбинаторное выражение
Комбинаторную логику можно рассматривать в качестве одной из вычислительных моделей, позволяющую выразить любую вычислимую функцию в виде композиции функций из небольшого конечного базиса. В этой задаче мы рассмотрим ограниченный вариант базиса 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. Выражение не содержит пробелов или символов, не указанных в грамматике.
Выходные данные
Выведите минимальное количество преобразований, необходимых для сведения заданной формулы к нормальной форме.