рекурсивный спуск

Ответ от Б Д[эксперт]
Поток сознания:
Стек - средство реализации рекурсии. М. б. просто использовать рекурсивные процедуры?
Для одной формулы в заданной грамматике существует много соответствующих ей деревьев.
Если строить дерево "справа налево", то получится дерево с длинной правой ветвью (глубина = количество знаков-1).
Не имеет смысла отдельно проверять правильность формулы - проверка естественно получается в ходе построения дерева.
Псевдокод функции:
function фДерево (строка) : тУзел
begin
if строка пустая then ошибка
создать пустой Узел
символ1 := первый символ строки, убрать из строки
if символ1 не терминальный then ошибка
if строка пустая then begin
Узел. средний := символ1
return Узел
end
Узел. левый := новый узел с вершиной = символ1
символ2 := первый символ строки, убрать из строки
if символ2 не знак then ошибка
Узел. средний := символ2
Узел. правый := фДерево (строка)
return Узел
end{фДерево}
Терминальные символы хранятся в символьном поле "средний" терминальных вершин (узлов) дерева.
Знаки хранятся в поле "средний" нетерминальных вершин.