Никак не понять ни о стеке, ни о рекурсии? ) Хорошо, вот вам код РНР, о котором я говорил. Стояла задача проверки списка из UL OL LI. Смотрите, может и наведет на мысли (скопировано пояснение и код).
Для простых тегов, типа параграфа, ссылки и т.п., все просто, а вот для тегов имеющих дочерние элементы, необходимо описывать правила. Вот появилось время немного, написал как можно это реализовать. Объявим массив, который будет описывать правила структуры вложений для некоторых тегов (в примере только те, что у вас - UL, OL, LI).
Сначала открывающие теги. Тегам OL, LI может предшествовать только тег LI, или же отсутствовать. Следовательно для них указываем правило - "пустой" или ''li". А так как мы всегда ожидаем в обязательном порядке вначале открывающий тег, то значение "пустой" загрузим в вершину стека при его инициализации. Это единственное значение стека, которое никогда не будет из него извлечено, и при верном вложении тегов, каждый новый открывающийся тег (вне вложений) будет будет соответствовать этому правилу. А в случае, если открывающему тегу списка предшествует тег не описанный в условии (вершина стека не равна ни одному тегу условий, а ключ проверяемого тега есть в условиях), то действует правило - первый элемент массива правил тега должен быть равен "пусто". Тегу LI всегда должен предшествовать тег указанный в условиях.
$order = array(
'ul' => array('','li'),
'ol' => array('','li'),
'li' => array('ul','ol')
);
$stack = array(''); //инициализация стека
$s = 'text...
<li>111</li>
<li>222</li>
text...';
//разобьем проверяемый текст на строки,
//так удобнее производить поиск и вывести строку с ошибкой
$s = explode("\r\n", $s);
$i = 1; //условно начальный номер строк
$error = null;
foreach($s as $v) {
$match = preg_match_all("/(<.*?>)/i", $v, $tag);
if($match) {
$tag = array_map('strtolower', $tag[0]);
foreach($tag as $t) {
$src = $t[1]!='/' ? 1 : 0; //определяем тип тега
$t = trim($t,'</> '); //получаем имя тега, в примере не учитываются его атрибуты, иначе нужно удалять их
if(!$t) {
$error = 'Ошибка в строке '.$i.' - некорректное имя тега!';
break 2;
}
if($src) { //открывающий тег
//если тег соответствует правилу вложения, то помещаем его в стек, вершина стека растет
if(!array_key_exists($t, $order) ||
array_key_exists($t, $order) && in_array($stack[0], $order[$t]) ||
array_key_exists($t, $order) && !$order[$t][0]
) array_unshift($stack, $t);
else {
$error = 'Ошибка в строке '.$i.' - отсутствует предшествующий тег '.implode(' или ', array_diff($order[$t],array(''))).'!';
break 2;
}
} else { //закрывающий тег
if($t==$stack[0]) array_shift($stack); //если тег соответствует открывающему, то извлекаем открывающий тег из стека, вершина стека убывает
else {
$error = 'Ошибка в строке '.$i.' - незакрыт предшествующий тег '.$stack[0].'!';
break 2;
}
}
}
}
$i++;
}
//вывод ошибок вложения
//и при их отсутствии проверка "чистоты" стека - отсутствие одиночного открытого тега
echo $error ? $error : count($stack)==1 ? 'Вложение корректное.' : 'Ошибка - отсутствует закрывающий тег '.$stack[0].'!';
//контроль стека
echo '<br><pre>';
print_r($stack);
