Условием пустоты стека является значение его вершины, равное nil.
function StackIsClear(var StackHead: Stack): Boolean;
begin
StackIsClear:= (StackHead= nil)
end;
Занесение элемента в стек
Для включения элемента в стек, необходимо создать новый элемент типа стек, затем инициализировать его информационное поле. В заключение изменить его указатель и указатель на первый элемент стека так, чтобы первым стал новый элемент.
procedure IncludeInStack(var StackHead: Stack; NewElem: TypeOfElem);
var
ServiceVar: Stack;
begin
{создание нового элемента}
new(ServiceVar);
ServiceVar^.Elem:= NewElem;
{созданный элемент сделать вершиной стека}
ServiceVar^.NextElem:= StackHead;
StackHead:= ServiceVar
end;
Выбор элемента из стека
При выполнении этой операции информационное поле элемента, находящегося в вершине стека, должно быть присвоено в качестве значения некоторой переменой, а сам элемент должен быть исключен из стека и уничтожен.
procedure SelectFromStack(var StackHead: Stack; var Result: TypeOfElem);
var
ServiceVar: Assoc;
begin
if StackHead <> nil then begin
{выбор элемента из вершины}
Result:= StackHead^.Elem;
{запоминание ссылки на старую вершину}
ServiceVar:= StackHead;
{исключение из стека и уничтожение элемента}
StackHead:= StackHead^.NextElem;
dispose(ServiceVar)
end
end;
Необходимо обратить внимание на введение вспомогательной переменной ссылочного типа ServiceVarдля осуществления удаления элемента. Типична ошибка, связанная с попыткой решить эту задачу через dispose(StackHead).
Разберем решение типичной задачи, связанной с обработкой стека.
Текст задания
Используя стек (считать уже описанными тип Stack с информационным элементом типа Char, функцию StackIsClear (проверка пустоты стека) и процедуры CreateStack (очистка стека), IncludeInStack (вставка элемента в стек), SelectFromStack (выборка элемента из стека)) решить следующую задачу: в текстовом файле f записана без ошибок формула следующего вида:
<формула>::= <цифра>|M(<формула>,<формула>)|m(<формула>,<формула>)
цифра::= 0|1|2|3|4|5|6|7|8|9
где M обозначает функцию max, а m – min. Вычислить (как целое число) значение данной формулы (например, M(5, m(6, 8)): 6).
Решение
program StackSample;
type
FileType= File of Char;
var
Source: FileType;
function formula(var t: FileType): integer;
type
TypeOfElem= Char;
Assoc= ^ElementOfStack;
ElementOfStack= record
Elem: TypeOfElem;
NextElem: Pointer
end;
Stack= Assoc;
var
S: Stack;
c, op, x, y: char;
procedure CreateStack (var StackHead: Stack);
begin
StackHead:= nil
end;
function StackIsClear(var StackHead: Stack): Boolean;
begin
StackIsClear:= (StackHead= nil)
end;
procedure IncludeInStack(var StackHead: Stack; NewElem: TypeOfElem);
var
ServiceVar: Stack;
begin
{создание нового элемента}
new(ServiceVar);
ServiceVar^.Elem:= NewElem;
{созданный элемент сделать вершиной стека}
ServiceVar^.NextElem:= StackHead;
StackHead:= ServiceVar
end;
procedure SelectFromStack(var StackHead: Stack; var Result: TypeOfElem);
var
ServiceVar: Assoc;
begin
if StackHead <> nil then begin
{выбор элемента из вершины}
Result:= StackHead^.Elem;
{запоминание ссылки на старую вершину}
ServiceVar:= StackHead;
{исключение из стека и уничтожение элемента}
StackHead:= StackHead^.NextElem;
dispose(ServiceVar)
end
end;
begin
reset(t);
CreateStack(S);
while not eof(t) do begin
read(t, c);
{обработка очередной литеры текста (литеры «(» и «,» игнорируются)}
if c in ['0'..'9','M','m'] then IncludeInStack(S, c)
else
if c= ')' then begin {конец формулы вида op(x, y)}
{в конце стека находится тройка op x y, она удаляется
из стека, выполняется операция op и результат
записывается в стек}
SelectFromStack(S, y);
SelectFromStack(S, x);
SelectFromStack(S, op);
case op of
'M'{max}: if x > y then c:= x else c:= y;
'm'{min}: if x < y then c:= x else c:= y
end;
IncludeInStack(S, c)
end
end; {of while}
{в стеке осталась одна цифра – значение всей формулы; цифра переводится в целое число}
SelectFromStack(S, c);
formula:= ord(c) - ord('0')
end;
begin
assign(Source, 'c:\temp\source.txt');
writeln(Formula(Source));
end.
Варианты заданий
1. Очереди
1. Type FR= file of real; За один просмотр файла f типа FR и без использования дополнительных файлов вывести элементы файла f в следующем порядке: сначала- все числа, меньшие a, затем- все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (a заданное число).
2. Type FR= file of real; За один просмотр файла f типа FR и без использования дополнительных файлов вывести элементы файла f в следующем порядке: сначала все числа из отрезка [a, b], и затем - все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (a и b- заданные числа a < b).
3. Содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного взаимного порядка, как среди цифр, так и среди остальных литер строки).
4. Содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее строчные гласные латинского алфавита (с сохранением исходного взаимного порядка, как среди гласных, так и среди остальных литер строки).
5. Содержимое текстового файла f, разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее символы ‘+’, ‘-‘, ‘*’ (с сохранением исходного взаимного порядка как среди этих символов, так и среди остальных литер строки).
6. type name= (George, Alex, Piter, Ann, Paul, John, Fred, Natalie, Robert); child= array [name, name] of boolean; children= file of name; Считая заданными имя n и массив d типа child (d[x]= true, если человек по имени y является ребенком человека по имени x), записать файл p типа children имена всех потомков человека с именем n в следующем порядке: сначала – имена всех детей, затем – всех его внуков, затем – его правнуков и т.д.
7. Описать процедуру, которая по одной очереди строит две новых: Queue1 из положительных элементов и Queue2 - из остальных элементов очереди (TypeOfElem= real).
8. Описать процедуру, которая подсчитывает количество элементов очереди, у которых равные "соседи".
9. Описать процедуру, которая определяет, есть ли в очереди хотя бы один элемент, который равен следующему за ним элементу.
10. Описать процедуру, которая в очереди переставляет в обратном порядке все элементы между первыми последним вхождением элемента E, если E входит в L не менее двух раз.
11. Описать процедуру, которая удаляет из очереди первый отрицательный элемент, если такой есть.
12. Описать процедуру, которая из очереди, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые "соседи".
13. Описать процедуру, которая формирует очередь Queue, включив в нее по одному разу элементы, которые входят хотя бы в одну из очередей Queue1 или Queue2.
14. Описать процедуру, которая формирует очередь Queue, включив в нее по одному разу элементы, которые входят в очередь Queue1, но не входят в очередь Queue2.
15. Описать процедуру, которая формирует очередь Queue, включив в нее по одному разу элементы, которые входят в одну из очередей Queue1 и Queue2, но в то же время не входят в другую из них.
2. Стеки
16. Вывести содержимое текстового файла t, выписывая литеры каждой его строки в обратном порядке.
17. Проверить, является ли содержимое текстового файла t правильной записью формулы следующего вида
<формула>::= <терм> | <терм> + <формула> | <терм> - <формула>
<терм>::= <имя> | (<формула>) | [<формула>] | {<формула>}
<имя>::= x | y | z
18. В текстовом файле Log записано без ошибок логическое выражение (ЛВ) в следующей форме.
<ЛВ>::= true | false | (ù <ЛВ>) | (<ЛВ> Ù <ЛВ>) | (<ЛВ> Ú <ЛВ>),
где знаки ù, Ù и Ú обозначают соответственно отрицание, конъюнкцию и дизъюнкцию. Вычислить (как boolean) значение этого выражения.
19. В текстовом файле t записан текст, сбалансированный по круглым скобкам:
<текст>::= <пусто> | <элемент> <текст>
<элемент>::= <буква> | (<текст>)
Требуется для каждой пары соответствующих открывающей и закрывающей скобок вывести номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров этих позиций закрывающих скобок.
20. Для задачи 19 вывести номера их позиций в тексте, упорядочив пары номеров в порядке возрастания номеров этих позиций открывающих скобок.
21. Под «выражением» будем понимать конструкцию следующего вида.
<текст>::= <терм> | <терм> <знак+–> <выражение>
<знак+–>::= + | –
<терм>::= <множитель> | <множитель>*<терм>
<множитель>::= <число> | <переменная> | (<выражение>) | <множитель>^<число>
<число>::= <цифра>
<переменная>::= <буква>
Где знак ^ обозначает возведение в степень. Постфиксной формой записи выражения aÙb называется запись, в которой знак операции размещен за операндами: abÙ.
Описать функцию value(postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в постфиксной форме в текстовом файле postfix. Использовать следующий алгоритм вычисления. Выражение просматривается слева направо. Если встречается операнд (число), то его значение (как целое) заносится в стек, а если встречается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция и ее результат записывается в стек. В конце концов, в стеке останется только одно число – значение всего выражения.
22. Описать процедуру translate(infix, postfix), которая переводит выражение, записанное в обычной (инфиксной) форме в текстовом файле infix, в постфиксную форму и в таком виде записывает его в текстовый файл postfix. Использовать следующий алгоритм перевода. В стек записывается открывающая скобка, и выражение просматривается слева направо. Если встречается операнд (число или переменная), то он сразу переносится в файл postfix. Если встречается открывающая скобка, то она заносится в стек, а если встречается закрывающая скобка, то из стека извлекаются находящиеся там знаки операций до ближайшей открывающей скобки, которая также удаляется из стека, и все эти знаки (в порядке их извлечения) записываются в файл postfix. Когда встречается знак операции, то из стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они записываются в файл postfix, после чего рассматриваемый знак заносится в стек. В заключение выполняются такие действия, как если бы встретилась закрывающая скобка.
23. Описать нерекурсивную процедуру infixprint(postfix), которая печатает в обычной (инфиксной) форме выражение, записанное в постфиксной форме в текстовом файле postfix. (Лишние скобки желательно не печатать.)
24. Описать процедуру, которая по одному стеку строит два новых: Stack1 из положительных элементов и Stack2 - из остальных элементов (TypeOfElem= real).
25. Описать процедуру, которая подсчитывает количество элементов стека, у которых равные "соседи".
26. Описать процедуру, которая определяет, есть ли в стеке хотя бы один элемент, который равен следующему за ним элементу.
27. Описать процедуру, которая удаляет из стека первый отрицательный элемент, если такой есть.
28. Описать процедуру, которая формирует стек Stack, включив в него по одному разу элементы, которые входят хотя бы в один из стеков Stack1 или Stack2.
29. Описать процедуру, которая формирует стек Stack, включив в него по одному разу элементы, которые входят в стек Stack1, но не входят в стек Stack2.
30. Описать процедуру, которая формирует стек Stack, включив в него по одному разу элементы, которые входят в один из стеков Stack1 и Stack2, но в то же время не входят в другой из них.
Двоичные деревья
Элементы двоичного дерева помимо информативной части имеют две ссылки – на нижний левый и на нижний правый элементы. Принцип построения двоичного дерева заключается в том, что очередной элемент в зависимости от значения информативной части должен попасть в правое (если информационная часть включаемого элемента больше информационной части корня) или левое (в противном случае) поддерево. При этом в рамках выбранного поддерева определение местоположения нового элемента производится аналогично.
p1
p1
p2 p3
p2 p3
имя узла
p4 p5 p4 p5
указатель правого указатель правого
поддерева поддерева
Рис. 9. Представление бинарного дерева в виде списковой структуры [3].
Данную структуру целесообразно описать следующим образом:
type
TypeOfElem= {};
Assoc= ^ElemOfTree;
ElemOfTree= record
Elem: TypeOfElem;
Left, Right: Pointer
end;
Рассмотрим основные операции, связанные с двоичными деревьями.
Поиск элемента в дереве
function FoundInTree(Elem: TypeOfElem; var Tree, Result: Pointer): Boolean;
var
ServiceVar: Assoc;
b: Boolean;
begin
b:= False;
ServiceVar:= Tree;
if Tree <> nil then
repeat
if ServiceVar^.Elem= Elem then b:= True
else
if Elem < ServiceVar^.Elem then ServiceVar:= ServiceVar^.Left
else ServiceVar:= ServiceVar^.Right
until b or (ServiceVar= nil);
FoundInTree:= b;
Result:= ServiceVar
end;
Включение элемента в дерево
Включение элемента в дерево реализуется путем во-первых, поиска вершины – предка нового элемента, во-вторых, непосредственным включением элемента в дерево по найденной позиции. Опишем процедуру поиска предка для нового элемента.
function SearchNode(Elem: TypeOfElem; var Tree, Result: Assoc): Boolean;
var
ServiceVar1, ServiceVar2: Assoc;
b: Boolean;
begin
b:= False;
ServiceVar1:= Tree;
if Tree <> nil then
repeat
ServiceVar2:= ServiceVar1;
if ServiceVar1^.Elem= Elem then {элемент найден} b:= True
else begin
{запоминание обрабатываемой вершины}
ServiceVar2:= ServiceVar1;
if Elem < ServiceVar1^.Elem then ServiceVar1:=
ServiceVar1^.Left
else ServiceVar1:= ServiceVar1^.Right
end
until b or (ServiceVar1= nil);
SearchNode:= b;
Result:= ServiceVar2
end;
Как видно из описания, эта функция подобна ранее рассмотренной функции поиска элемента дерева (FoundInTree), но в качестве побочного эффекта фиксируется ссылка на вершину, в которой был найден заданный элемент (в случае успешного поиска), или ссылка на вершину, после обработки которой поиск прекращен (в случае неуспешного поиска). Сама процедура включения элемента в дерево будет иметь следующее описание.
procedure IncludeInTree(Elem: TypeOfElem; var Tree: Assoc);
var
Result, Node: Assoc;
begin
if not SearchNode(Elem, Tree, Result) then begin
{формирование новой вершины в дереве}
new(Node);
Node^.Elem:= Elem;
Node^.Left:= nil;
Node^.Right:= nil;
if Tree= nil then
{если дерево пусто, то созданный элемент сделать вершиной дерева}
Tree:= Node
else
{подсоединить новую вершину к дереву}
if Elem < Result^.Elem then Result^.Left:= Node
else Result^.Right:= Node
end
end;
Двоичное дерево можно рассматривать как рекурсивную структуру данных, состоящую из корневой записи, указывающей на левое и правое поддерево. Оба поддерева имеют такую же структуру: корень поддерева и правое и левое поддеревья. При этом, для представления дерева рекурсивной динамической структурой целесообразно модифицировать описание типа дерева, данное выше. А именно, удобнее изменить тип ссылок на левое и правое поддеревья с нетипизированного (Pointer) на типизированный:
type
TypeOfElem1= {};
Assoc1= ^ElemOfTree1;
ElemOfTree1= record
Elem: TypeOfElem1;
Left, Right: Assoc1
end;
Опишем процедуру вставки элемента рекурсивно.
procedure IncludeInTree2(NewElem: Assoc1; var SubTree: Assoc1);
begin
if SubTree= nil then begin
SubTree:= NewElem;
NewElem^.Left:= nil;
NewElem^.Right:= nil;
end
else
if NewElem^.Elem < SubTree^.Elem then
IncludeInTree2(NewElem, SubTree^.Left)
else
IncludeInTree2(NewElem, SubTree^.Right)
end;
Удаление элемента дерева
Проблема реализации данной операции состоит в том, что в общем случае, в удаляемую вершину входит одна связь, а выходят две. Поэтому, необходимо найти подходящий элемент дерева, который можно было бы вставить на место удаляемого. Этот элемент является либо самым правым элементом левого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по левой ветви, а затем, переходить в очередные вершины по правым ветвям до тех пор, пока очередная такая ссылка не будет равна nil), либо самый левый элемент правого поддерева (для достижения этого элемента необходимо перейти в следующую вершину по правой ветви, а затем, переходить в очередные вершины по левым ветвям до тех пор, пока очередная такая ссылка не будет равна nil). Процедура исключения элемента из двоичного дерева должна различать тои случая:
1. элемента с заданной информативной частью в дереве нет;
2. элемент с заданной информативной частью имеет не более одной ветви;
3. элемент с заданной информативной частью имеет две ветви.
procedure DeleteElemOfTree(var Tree: Assoc1; Elem: TypeOfElem1);
var
ServiceVar1: Assoc1;
procedure Del(var ServiceVar2: Assoc1);
begin
if ServiceVar2^.Right= nil then begin
ServiceVar1^.Elem:= ServiceVar2^.Elem;
ServiceVar1:= ServiceVar2;
ServiceVar2:=ServiceVar2^.Left
end
else Del(ServiceVar2^.Right)
end;
begin
{удаление элемента с информативным полем равным Elem из дерева Tree}
if Tree= nil then
{первый случай процедуры удаления}
writeln('Элемент не найден')
else
{поиск элемента с заданным ключом}
if Elem < Tree^.Elem then DeleteElemOfTree(Tree^.Left, Elem)
else
if Elem > Tree^.Elem then
DeleteElemOfTree(Tree^.Right, Elem)
else begin
{элемент найден, необходимо его удалить}
ServiceVar1:= Tree;
{второй случай процедуры удаления}
if ServiceVar1^.Right= nil then
Tree:= ServiceVar1^.Left
else
if ServiceVar1^.Left= nil then
Tree:= ServiceVar1^.Right
else
{третий случай процедуры удаления}
Del(ServiceVar1^.Left)
end
end;
Вспомогательная рекурсивная процедура Del вызывается лишь в третьем случае процедуры удаления. Она переходит к самому правому элементу левого поддерева удаляемого элемента, а затем заменяет информационное поле удаляемого на значение поля найденного элемента.
Вывод элементов дерева
Данная задача также может быть решена с помощью механизма рекурсии.
procedure PrintTree(Tree: Pointer);
var
ServiceVar: Assoc1;
begin
ServiceVar:= Tree;
writeln(ServiceVar^.Elem);
if ServiceVar^.Right <> nil then PrintTree(ServiceVar^.Right);
if ServiceVar^.Left <> nil then PrintTree(ServiceVar^.Left);
end;
Разберем решение типичной задачи, связанной с обработкой двоичных деревьев.
Текст задания
Описать процедуру copy(T, T1) которая строит T1 – копию дерева T.
Решение
procedure CopyTree(T: Tree; var T1: Tree);
begin
if T= nil then T1:= nil
else
begin
new(T1);
T1^.Elem:= T^.Elem;
CopyTree(T^.Left, T1^.Left);
CopyTree(T^.Right, T1^.Right)
end
end;
Варианты заданий
1. Во внешнем текстовом файле PROG записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и/или цифр. Напечатать в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождений в программу. (Учесть, что в идентификаторах одноименные прописные и строчные буквы отождествляются, что внутри литерных значений, строк-констант и комментариев последовательности из букв и цифр не являются идентификаторами и что в записи вещественных чисел может встретится бука Е или е.) Для хранения идентификаторов использовать дерево поиска, элементами которого являются пары – идентификатор и число его вхождений в текст программы.
2. Решить задачу 1, но вместе с каждым идентификатором печатать в возрастающем порядке номера всех строк текста программы, в которых он встречается.
3. Решить задачу 1 при условии, что максимальная длина идентификаторов неизвестна.
4. Решить задачу 2 при условии, что максимальная длина идентификаторов заранее не известна.
5. Деревом поиска, или таблицей в виде дерева, называется двоичное дерево, в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа - с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (TypeOfElement) допускает применение операций сравнения). Считая описанным тип дерево и тип файл: type file1= file of TypeOfElement; Определить функцию или процедуру, которая проверяет, входит ли элемент Е в дерево поиска Т.
6. Для дерева поиска и файла задачи 5 определить функцию или процедуру, которая записывает в файл f элементы дерева поиска Т в порядке их возрастания.
7. Для дерева поиска и файла задачи 5 определить функцию или процедуру, которая добавляет к дереву поиска Т новый элемент Е, если его не было в Т.
8. Для дерева поиска и файла задачи 5 определить функцию или процедуру, которая по файлу f, все элементы которого различны, строит соответствующее дерево поиска Т.
В последующих задачах используются двоичные деревья, описанные следующим образом: type TypeOfElement= …; {тип элементов дерева} Tree= ^Assoc; Assoc= record Elem: TypeOfElem; Left, Right: Tree end; При этом, параметры T, T1, T2 обозначают деревья, а параметры E- величину типа TypeOfElement.
9. Используя очередь или стек описать процедуру или функцию, которая присваивает параметру E элемент самого левого листа непустого дерева T (лист – вершина, из которой не выходит не одной ветви).
10. Используя очередь или стек описать процедуру или функцию, которая определяет число вхождений элемента E в дерево T.
11. Используя очередь или стек описать процедуру или функцию, которая вычисляет среднее арифметическое всех элементов непустого дерева T (TypeOfElem= real).
12. Используя очередь или стек описать процедуру или функцию, которая заменяет все отрицательные элементы дерева T на их абсолютные величины (TypeOfElem= real).
13. Используя очередь или стек описать процедуру или функцию, которая меняет местами максимальный и минимальный элементы непустого дерева T, все элементы которого различны (TypeOfElem= real).
14. Используя очередь или стек описать процедуру или функцию, которая выводит элементы из всех листьев дерева T (TypeOfElem= char).
15. Используя очередь или стек описать процедуру или функцию, которая выводит все элементы дерева T по уровням: сначала – из корня дерева, затем (слева направо) – из вершин, дочерних по отношению к корню, затем (также слева направо) – из вершин, дочерних по отношению к этим вершинам, и т.д. (TypeOfElem= integer).
16. Используя очередь или стек описать процедуру или функцию, которая находит в непустом дереве T длину (число ветвей) пути от корня до ближайшей вершины с элементом E; если E не входит в T, за ответ принять –1.
17. Используя очередь или стек описать процедуру или функцию, которая подсчитывает число вершин на n- ом уровне непустого дерева T (корень считать вершиной 0-го уровня).
18. Описать рекурсивную процедуру или функцию, которая определяет, входит ли элемент E в дерево T.
19. Описать рекурсивную процедуру или функцию, которая определяет число вхождений элемента E в дерево T.
20. Описать рекурсивную процедуру или функцию, которая вычисляет сумму элементов непустого дерева T (TypeOfElem= real).
21. Описать рекурсивную процедуру или функцию, которая находит величину наибольшего элемента непустого дерева T (TypeOfElem= real).
22. Описать рекурсивную процедуру или функцию, которая печатает элементы из всех листьев дерева T (TypeOfElem= char).
23. Описать рекурсивную процедуру или функцию, которая определяет максимальную глубину непустого дерева T, т.е. число ветвей в самом длинном из путей от корня до листьев.
24. Описать рекурсивную процедуру или функцию, которая подсчитывает число вершин на n-ом уровне непустого дерева T (корень считать вершиной 0-го уровня).
25. Рекурсивно и не рекурсивно описать функцию equal(T1, T2), проверяющую на равенство деревья T1 и T2.
26. Описать логическую функцию same(T), определяющую, есть ли в дереве T хотя бы два одинаковых элемента.
27. Формулу вида
<формула>::= <терминал> | (<формула> <знак> <формула>)
<знак>::= + | - | *
<терминал>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
можно представить в виде двоичного дерева (“дерева-формулы) с (TypeOfElem= char) согласно следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1s f2) – деревом, в котором корень – это знак s, а левое и правое поддеревья – это соответствующие представления формул f1b f2. Описать рекурсивную процедуру или функцию, которая вычисляет как целое число значение дерева-формулы T.
28. Описать рекурсивную процедуру или функцию, которая по формуле из текстового файла f строит соответствующее дерево-формулу (см. задачу 27) T.
29. Описать рекурсивную процедуру или функцию, которая выводит дерево-формулу (см. задачу 27) T в виде соответствующей формулы.
30. Описать рекурсивную процедуру или функцию, которая проверяет, является ли двоичное дерево T деревом-формулой (см. задачу 27).
Заключение