Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»

Шаг 0. Начни с первого, в данном порядке, пути

В одних порядках это - пустой путь к корню дерева, в других его необходимо предварительно построить!

Шаг i+1

(если можно идти в направлении D₁,) иди в направлении D₁,

(если нет, но можно идти в направлении D₂,) иди в направлении D₂,

(если нет, но можно идти в направлении D₃,) иди в направлении D₃,

• 
  нужно запоминать ссылки на корни деревьев, которые еще предстоит обработать - самое простое - класть их в конец некоторой (динамической!) последовательности.
  
• 
  для реализации подъема нужно вытащить ссылку на вершину из хранилища; в зависимости от вида обхода, это может означать как "вытаскивание" как с того же, так и другого конца последовательности.
  

Сказанное определяет тип последовательности-хранилища: это либо стек, реализующий "вытаскивание" с того же конца, либо очередь, реализующая "вытаскивание" с противоположного конца. (См. "Абстрактные линейные типы").

{ более короткие ветки (слова, пути) идут в перечислении раньше более длинных}

procedure КЛП(root:pTree);

var

stack:pStack; { реализация - см. "Абстрактные линейные типы"}

begin

Create(stack);

if root<>nil then push(stack,root);

while not empty(stack) do

begin

pop(stack,pt); {подъем наверх}

begin

if left<>nil {можешь идти налево?}

then {тогда иди, но сохрани правую ссылку}

begin pt:=left; if right<>nil then push(stack,right) end

else {налево нельзя}

if pt^.right<>nil {- можно ли направо?}

then pt:= pt^.right

end;

end;
{пример обхода в ширину - ветви одинаковой длины ("буквы" left, right) соседствуют в перечислении}

procedure (root:pTree);.

var

pt:pNode;{ссылка на текущую вершину}

begin

Create(Queue); {создать очередь}

while not Empty(Queue) {очередь не пуста} do

begin

Get(Queue, pt); {Вывести Из Очереди}

if pt!.left<>nil then Put(Queue, pt!.left);

if pt!.right<>nil then Put(Queue, pt!.right);

end;

end;
Замечание. Деревья просто определяются рекурсивно, а потому – для проявления эрудиции – нетрудно дополнить ответ рекурсивными вариантами обхода «в глубину». Но – не заменять ими итеративный вариант!

1. 
   Вычисление функции значения/именования, т.е. нахождение значения по его обозначению и обратная задача.
   
2. 
   Формальная обработка («редактирование») текстов как собственно последовательностей, никак не связанная с ролью текстов как обозначений.
   
3. 
   Формальные вычисления - порождение текста результата некоторого преобразования значений по тексту ее аргументов
   

Определим арифметическое выражение (в полноскобочной инфиксной записи) как последовательность символов, являющуюся

1. 
   либо термом, т.е.
   

1. 
   либо именем константы вида b₁… b_n.c₁… c_m , где
   

2. 
   либо именем переменной вида d₁… d_k, где
   

2. 
   либо строкой вида (E₁)f(E₂), где E₁,E₂ - выражения, а f - один из знаков +,-,*,/
   

pNode=^tNode;

tNode= record

Name:string;

Val:integer;

left,right:pNode;

end;
Очевидно, это не очень экономное решение в смысле расхода памяти - для двух термов с одинаковым значением мы сохраняем значение дважды, а остальные (содержащие знаки операций) вершины вообще изначально не имеют значения. Обычно значения термов и промежуточные результаты сохраняют во внешних по отношению к дереву таблицах.
{вычисление элементарного выражения}

function AtomVal(root:pExpr):T;

begin

with root^ do

'+': AtomVal:=left^.Val+right^.Val;

'-': AtomVal:=left^.Val-right^.Val;

'*': AtomVal:=left^.Val*right^.Val;

'/': AtomVal:=left^.Val/right^.Val;

{для простоты, опускаем обработку исключения - деления на 0}

end; end;
{выяснение типа вершины}

function NodeType(pt:pNode):char;

begin

with pt^ do

then NodeType='t'

else NodeType='f'

end;
{поиск атома, лежащего ниже данной вершины}

{идея: вычисление -свойства found:= ptpNode (ptnil & pt^.leftnil & pt^.rightnil) }

{см."Вычисление свойств"}

{предусловие: вершина pt содержит знак операции, NodeType(pt)='f'}

procedure FindAtom(var pt:pNode; var stack: pStack);

var found:Boolean;

begin

begin

while not found do

begin

if NodeType(left) ='f'

else if NodeType(right)='f'

then begin push(pt,stack); pt:=right end

else

found:=true

end;

end;

function ExpVal(root:pExpr):T;

var

stack:pStack;

{реализацию см. "Абстрактные линейные типы данных"}

found:Boolean; {есть еще атомы?}

RootType,LeftType,RightType:char; {{'t','f')}

begin

Create(stack); UpperType:=NodeType1(root);

while not empty(stack) {= есть невычисленные операции} do

begin

{следующий поиск начинаем c вершины, ближайшей к вычисленному атому}

{Вычисли значение атомарного выражения}

pt^.val:= AtomValue(pt);

{Сократи дерево}

destroy(pt^.right); pt^.right:=nil;

destroy(pt^.left); pt^.left:=nil;

end;

{Дерево состоит из одной вершины}

end;
Замечание. Побочным (и не очень желательным) эффектом простоты нашего алгоритма является уничтожение самого дерева. В реальности, мы можем не уничтожать вычисленные термы, а лишь помечать их как уже вычисленные.

1. 
   Анализ термов.
   

type tSetOfChar=set of char;

procedure FindException

(s:string; start,finish:Cardinal; alphabet:tSetOfChar; position:Cardinal; found:boolean);

{идея: проверка свойства found= position [start,end] (s[position]  alphabet)}

{см."Вычисление свойств" и "Поиск"}

begin

while (position<=finish) and (not found) do

if s[position] in alphabet then inc(position) else found:=true;

end; { function FindException }

{проверка имени константы}

function ConstantName(s:string):boolean;

var

position, {позиция "исключения" - см. procedure FindException }

found:boolean; {"исключение" найдено}

begin

len:=Length(s); ConstantName:=false;

if (position=1) or (position=len) or (not found)

then {нет обязательной внутренней не-цифры} exit; {завершаем}

if s[position]<>'.'

then {эта не-цифра - не точка} exit; {завершаем}

{есть ли не-цифры после точки?}

FindException(s,position+1,len,['0'..'9'],position,found);

ConstantName:=not found

end;
{проверка имени переменной - еще проще}

function VariableName(s:string):boolean;

var

position, {позиция "исключения" - см. procedure FindException }

found:boolean; {"исключение" найдено}

begin

len:=Length(s); VariableName:=false;

if not (s[1] in ['a'..'z']) then exit;

FindException(s,2,len,['0'..'9']+['a'..'z'],position,found);

VariableName:=not found

end;

2. 
   Анализ (сложных) выражений.
   

Определим понятие расширенного (или просто р-) выражения как строки вида (E₁)F(E₂), где E₁,E₂ - произвольные, в том числе пустые строки, а F - произвольная непустая строка. Мотивация - любому невырожденному дереву однозначно сопоставляется некоторое р-выражение.

 терм 'x', если Тип(E₁)=Тип(E₂)='t' и Тип(F)='f'

Reduce((E₁)F(E₂))= 

 '', в противном случае

(смысл прост - результатом вычисления правильного выражения является терм, а результат вычисления неправильного выражения не определен)
Идея алгоритма: Выражение правильно  тип результата формального вычисления = терм.
{расширенный тип вершины}

function ExtentedNodeType(pt:pNode):char;

var len:Cardinal; {длина строки}

begin

ExtendedNodeType:='';

if pt=nil { тип пустого слова неопределен}

then exit; {= завершить определение значения функции }

with pt^ do

begin

if len=0 then exit;

if (Len=1) and (name[1] in ['+','-','*','/']) and (left<>nil) and (right<>nil)

then begin ExtendedNodeType:='f'; exit end;

if (left=nil) and (right=nil) and

(ConstantName(pt^.name) or VariableName(pt^.name)

then ExtentedNodeType:='t'

end; {with}

end; { function ExtentedNodeType }

{теперь не уверены, что найдутся правильные атомы!}

{но, в таком случае, обязательно найдется не правильный }

{см. определение ниже в теле процедуры}

procedure FindExtendedAtom(var pt:pNode; var stack: pStack);

var found:Boolean;

begin

with pt^ do

found:=false;

while not found do

begin

LeftType= NodeType(left);

RightType=NodeType(right);

if (UpperType<>'f') or (LeftType='') or (RightType='')

then

{дальше искать нечего, формально считаем - найден "не правильный" атом}

else if LeftType='f'

then begin push(pt,stack); pt:=pt^.left end

else if RightType='f'

then begin push(pt,stack); pt:=pt^.right end

else {UpperType='f' & LeftType='t' & RightType='t'}

{  найден правильный атом }

found:=true

end; {while}

end; {with }

end; { procedure FindAtom }
{формальное вычисление расширенного элементарного выражения}

function ExtendedAtomVal(root:pExpr):string;

begin

with root^ do

(ExtendedNodeType(left)='t') and

(ExtendedNodeType(right)='t') {корректный атом}

then ExtendedAtomVal:='x' {сгодиться любой терм!}

else ExtendedAtomVal:='';

end;
function ExpressionCorrect(root:pExpr):boolean;

begin

result:=true;

RootType:=ExtendedNodeType(root);

case RootType of

'': result:=false;

'f': push(stack,root);

end;

begin

FindExtendedAtom(pt,stack);

{Формальное "вычисление"}

pt^.Name:=ExtendedAtomValue(pt);

if NodeType(pt)=''

{если результат элементарного вычисления неопределен}

then Result:=false {то результат всего вычисления - и подавно}

else

destroy(pt^.right); pt^.right:=nil;

destroy(pt^.left); pt^.left:=nil;

end; {if}

end; {while}

Result:=(NodeType(root)='t')

end;