eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Комбинаторное выражение

Комбинаторное выражение

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

prb7494_1.gif

После совершения замены мы должны повторять этот процесс, пока не останется ни одного подходящего подвыражения. Это окончательное выражение и является нормальной формой исходного.

Например в выражении CIC(CB)I мы можем совершить следующее присваивание литералов

prb7494_2.gif

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

prb7494_3.gif

Еще один пример выражения: B((CK)I)IC. Редуцируем комбинацию B:

prb7494_4.gif

Теперь редуцируем последнее I:

prb7494_5.gif

И завершим вычисления еще двумя редукциями:

prb7494_6.gif

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

prb7494_7.gif

ведет к тому же результату что и

prb7494_8.gif

Однако, как Вы видите, количество сокращений отличается: 3 в первом случае и 2 во втором. Перед нами появляется интересная задача - найти порядок вычислений с минимальным количеством сокращений для данной формулы.

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

Входные данные

Единственная строка содержит комбинаторное выражение, соответствующее вышеприведенной грамматике. Длина выражения не превышает 30000. Выражение не содержит пробелов или символов, не указанных в грамматике.

Выходные данные

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

Пример

Входные данные #1
C(K(II)(IC))
Выходные данные #1
2
Входные данные #2
CIBI
Выходные данные #2
3
Входные данные #3
BBBBBCCCCCKKKKKIIIII
Выходные данные #3
15
Источник 2014 ACM NEERC, Northern Subregion, November 8, Problem C