PHP::SimpleXML. Часть 2. XML дерево

В заключительной части цикла статей посвященного работе с SimpleXML, будет рассмотрена довольно распространенная задача: построение XML дерева.

Требования

• Отображение в виде дерева содержимого любого XMLфайла с правильной структурой;
• Возможность сворачивать и разворачивать ветви;
• Атрибуты элементы выводятся в строку рядом с ним;
• Текст элемента так же пишется рядом с названием элемента, но в скобках;

Для того, что бы лучше понять, что же все-таки мы хотим сделать, можно посмотреть на уже готовый пример: http://st-programming.ru/simple_xml/index.php

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

Дерево представляет собой обычный вложенный список. Для добавления функциональности (сворачивание и разворачивание) и нормального внешнего вида используется плагин для JQuery – Treeview (скачать)...

Delphi::Стеки. Часть 2. Расстановка скобок

В первой части цикла статей был реализован класс стека. Сейчас мы рассмотрим применение стека для решения одной, в общем-то, классической задачи по программированию.

Задача

Необходимо проверить правильность расстановки скобок “(), {}, []” в выражении. То есть проверить, все ли скобки закрыты, соответствует ли закрывающаяся скобка открывающейся, нет ли лишних закрывающихся скобок и тд.

К примеру, такое выражение 2 * ( 3 – [ x+ 3 ] / 15 ) – { 2 + 3 } * 5 проверку пройдет, а 2 * ( 3 – [ x+ 3 ) / 15 ] – { 2 + 3 } * 5 уже нет.

Алгоритм решения

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

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

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

Для лучшего понимания это можно рассмотреть на примере.

Возьмем выражение 2 * ( 3 – [ x + 3 ] / 15 }– { 2 + 3 }* 5].

Находим первую открывающееся скобку, это будет «(», кладем ее в стек, идем далее. Доходим до скобки «[», тоже кладем ее в стек. К тому времени, как мы дойдем до скобки «]», стек уже будет «(, [», проверяем вершину стека: «[» и скобку «]», как видно они пара. Следовательно скобку [ выталкиваем из стека. Идем далее до скобки }. На это время в стеке у нас осталась только «(», очевидно, что парой для } она не является, получаем ошибку. На этом, в общем-то программу можно прервать, то лучше дойти до конца и получить полный список ошибок. Скобку { кладем в стек, после проверки со следующей }, так как они пара, то { можно вытолкнуть. В стеке опять осталась только (. Дошли до последней скобки ]. Снова получаем ошибку, так как ( и ], собственно не пара. И так же, поскольку после обхода, у нас в стеке все еще осталась скобка (, то получаем еще одну ошибку, что не все скобки закрыты...