В этой задаче речь пойдет о вымышленных языках BHTML и BCSS, которые слегка напоминают HTML и CSS. Внимательно ознакомьтесь с условием задачи, так как схожесть лишь отдаленная, а в задаче используются крайне упрощенные аналоги.
Задан BHTML-документ, который похож на HTML, но значительно проще. Записывается он как последовательность открывающих и закрывающих тегов. Тег вида «<имятега>» называется открывающим, а тег вида «</имятега>» — закрывающим. Кроме того, есть самозакрывающиеся теги, которые записываются в виде «<имятега/>» и в этой задаче полностью эквивалентны «<имятега></имятега>». Все имена тегов в этой задаче — строки из строчных латинских букв, имеющие длину от 1 до 10 символов. Некоторые теги могут иметь одинаковые имена.
Теги в документе образуют правильную скобочную последовательность, то есть из заданной последовательности можно получить пустую с помощью операций:
- удалить любой самозакрывающийся тег «<имятега/>»,
- удалить пару открывающий-закрывающий тег, которые идут подряд (в таком порядке) и имеют одинаковые имена, то есть подстроку «<имятега></имятега>».
Например, вам может быть задан документ «<header><p><a/><b></b></p></header><footer></footer>», но не могут быть заданы документы «<a>», «<a></b>», «</a><a>» или «<a><b></a></b>».
Очевидно, для каждого открывающего тега существует единственный парный закрывающий — каждая такая пара называется элементом. Самозакрывающийся тег — тоже элемент. Говорят, что один элемент вложен в другой, если теги первого находятся между тегами второго. Считается, что никакой элемент не вложен сам в себя. Например, в примере выше элемент «b» вложен в «header» и в «p», но не вложен в «a» и «footer», а также не вложен в самого себя («b»). Элемент «header» имеет три вложенных в него элемента, а «footer» — ноль.
Правила BCSS нужны для назначения стилей при выводе элементов документов BHTML. Каждое правило записывается в виде последовательностей слов «x1 x2 ... xn». Под это правило попадают все такие элементы t, которые удовлетворяют пунктам из списка:
- существует последовательность вложенных элементов с именами тегов «x1», «x2», ..., «xn» (то есть второй элемент вложен в первый, третий во второй и так далее),
- эта последовательность заканчивается элементом t.
Например, правилу «a b» удовлетворяют все такие элементы «b» для которых существует элемент «a», в который они вложены. Правилу «a b b c» удовлетворяют все такие элементы «c» для которых существует три элемента «a», «b», «b», что в цепочке «a»-«b»-«b»-«c» каждый очередной элемент вложен в предыдущий.
Напишите программу, которая по заданному BHTML-документу и набору BCSS-правил определяет количество элементов, которые удовлетворяют каждому из правил.