Задачи
Восстановление HTML файла
Восстановление HTML файла
Петя недавно скачал поврежденный HTML файл. Он выглядит как обычный HTML файл, но в нем есть некоторые несоответствия тэгов. Ваша задача - удалив минимальное количество открывающихся и закрывающихся тэгов сделать так, чтобы структура тэгов стала правильной.
Более формально, HTML файл состоит из произвольных символов с ASCII кодами из диапазона от \textbf{32} до \textbf{126}, а также Linux-style переводов строки (символов с кодом \textbf{10}). Тэги открываются следующим образом: <\textbf{Имя тэга Параметры}> и закрываются следующим образом <\textbf{Имя тэга}>. \textbf{Имя тега} - строка, состоящая из больших и маленьких латинских букв, которые считаются различными. \textbf{Имя тэга} отделяется от \textbf{Параметров} как минимум одним пробелом (но не переводом сроки). Параметры могут содержать произвольные допустимые ASCII символы кроме \textbf{<}, \textbf{>} и переводов строк. Также допускаются открывающиеся тэги без параметров и записываются в следующей форме: <\textbf{Имя Тэга}>.
HTML файл счиается правильным, если каждому открывающемуся тэгу можно привести в соответствие следующий далее в файле закрывающийся тэг таким образом, чтобы часть файла между этими тэгами также представляла собой правильный HTML файл, и аналогично можно привести в соответствие каждому закрывающемуся тэгу ровно один окрывающийся тэг идущий ранее в файле. HTML файл, не содержащий тэгов, также является правильным. Окрывающийся тэг считается соответствующим закрывающемуся, если у них одинаковое имя тэга.
\InputFile
Входной файл представляет из себя поврежденный HTML файл, который требуется исправить. Его длина не превосходит \textbf{10000} байт. Количество открывающихся и закрывающихся тэгов не превышает \textbf{500}. Символы \textbf{<} и \textbf{>} не встречаются нигде, кроме окрывающихся и закрывающихся тэгов.
\OutputFile
Выведите единственное целое число - минимальное количество окрывающихся/закрывающихся тэгов, которые требуется удалить, чтобы файл оказался правильным HTML файлом.
Входные данные #1
<a href=http://kruzhok.newmail.ru> <b someone has corrupted this file> It was a good file before... </a> </b>
Выходные данные #1
2