Различные объединения типов. Записи типов с вариантами.

Синтаксис: список полей есть выражение вида

L=N₁:T₁,…,N_m:T_m.

где N_i – список идентификаторов

T_i – произвольный тип, кроме файла.

record

L

end;

Общий синтаксис типа record:

record

L₀ {Знакомый нам синтаксис – общая часть записи. В любой переменной данного типа присутствуют поля из этого списка}

case S:T_s of

c₁:(L₁); Поле S типа T_s также присутствует во всех значениях типа.

. . .

c_m:(L_m); вариантная часть записи

end; S – селектор

end;

c₁,…,c_m – значения типа T_s

Предполагается, что в значении данного типа присутствуют лишь поля одного из списков L_i в зависимости от значения поля S.

* x.S=c_i 

x:record

L₀, S : T_s : L_i

end;

N₁ N₂ N₃

type

tInfo=record

case этоInteger:boolean of

true: (IntInfo:integer);

false: (CharInfo:char);

end;

end;

Условие * не проверяется автоматически.

x.этоInteger:=true;

write(x.CharInfo);

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

Пример: невозможно параметрическое определение типа: stack of T.

Создание дерева. Перевод из префиксной записи. Представление записи.

Дан текстовый файл exp, содержащий правильно построенное выражение.

Требуется создать дерево:

((x+1)*y)/2

/*+x1y2

Пока в выражении идут имена функций идём налево.

Натыкаемся на старую проблему: нужно вернуться на предыдущую вершину.

Решение: сохранять ссылки на вершины со свободным правым концом в стеке.

procedure Create(var exp:text;var root:pNode);

var stack:tStack {Стек ссылок на вершины}

c:char; pt:pNode;

begin {Корень создаём отдельно}

reset(exp);

read(exp,c);

root:=NewNode(c); {Создаём вершину с содержимым атрибутом c}

push(stack,root);

while not eof(exp) do

begin

read(exp,c);

while c in [‘+’ , ’-‘ , ’/’ , ’*’] do

begin

pt^.left:=NewNode(c);{Ссылка на текущую вершину дерева}

pt:=pt^.left;

push(stack,pt);

read(exp,c);

end;

pt^.left:=NewNode(c);

read(exp,c);

pt^.right:=NewNode(c);

pt:=pt^.right;

pop(stack,pt);

end;

end;

Примечание: на практике exp нельзя использовать как логическое имя файла! Здесь это использовалось в силу того, что expression (англ.) – выражение.

Анализ алгоритма вычисления. Дерево как последовательность ветвей.

Дано выражение в текстовом файле. Вычислить значение выражения.

Дерево – естественная форма представления выражений, но неэффективно по расходу памяти. Если алгоритм сводится к последовательной обработке компонент некоторой последовательности в естественном порядке, не нужно держать в памяти всю последовательность. В алгоритме вычисления в каждый момент времени используются сведения лишь об одной ветке дерева (ссылка на которую хранится в стеке).

function NewNode(c:char):pNode;

var NewPt:pNode;

begin

new(NewPt);

NewPt^.info:=c;

NewPt^.left:=nil;

NewPt^.right:=nil;

NewNode:=NewPt;

end;

type

tInfo=record

case этоInteger:boolean of

true (IntInfo:integer);

false (CharInfo:char);

end;

end;

function ExpVal(var exp:text;VarVal: tVarVal):integer; {tVarVal  tVariable)}

var stack:tStack; {tStack of tInfo}

begin

create(stack); {Стек символов}

ReadChar(exp,f);

ReadChar(exp,x);

push(stack,f);

push(stack,x);

while not eof(exp) do

begin

{Пока не нашли атом, читай символы и складывай в стек}

pop(stack,x);

pop(stack,f); {/*+x1y2}

ReadChar(exp,c);

while not Atom(f,x,y) do

begin

push(stack,f);

push(stack,x);

push(stack,y);

pop(stack,x);

pop(stack,f);

ReadChar(exp,c);

end;

push(stack,AtomVal(f,x,y));

end;

pop(stack,x);

ExpVal:=x.IntInfo;

end;

Мы упоминали об относительности взгляда на структуры (деревья, графы) как на структуры данных и структуры управления. То, что раньше мы воспринимали как структуру данных (в первом алгоритме), стало трассой вычисления.