Преобразование из инфиксной в постфиксную

1е правило: удаление скобок.

Если очередной символ в исходной строке – операнд, он переносится в результирующую строку.

Если (, +, -, *, /, ^ - он заносится в стек.

Если) – то из стека извлекаются все знаки операций и заносятся в результирующую строку до тех пор, пока не встретится открывающаяся скобка.

(A+B)*(C+D) à AB+CD+*

2е правило: приоритеты операций

Если очередной символ исходной строки – знак операции, то перед занесением в стек приоритет данной операции (х) сравнивается с приоритетом операции, находящейся в вершине стека (у), если приоритет у >=х, то знак операции, находящейся в вершине стека записывается в результирующую строку.

Это продолжается до тех пор, пока в вершине стека не будет операции, приоритет которой меньше приоритета текущей операции, после этого текущая операция заносится в стек.

A/B*C+D à AB/C*D+

Постфиксная запись представляет собой такую запись арифметического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +. Здесь операндами операции * будут b и c (два ближайших операнда), а операндами операции + будут а и составной операнд b c *. Эта запись удобна тем, что она не требует скобок. Например, для выражения (a + b) * c постфиксная запись будет a b + c *. В этой записи не требуется ставить скобки для того, чтобы изменить порядок вычисления, зависящий от приоритета операций, как в исходном выражении.

Вычисление выражения, записанного в постфиксной форме: каждая операция ссылается к предшествующим двум операндам этой строки; один из операндов может быть результатом выполнения предыдущей операции. Предположим, что всякий раз, как просчитываем операнду, помещаем его в стек. Когда достигаем операции, то отнесенные к ней операнды будут двумя верхними эл-тами стека. Можно извлечь эти 2 операнды и осуществить над ними указанную операцию. Затем результат записать в стек. Тем самым он станет доступным в качестве операнды применительно к следующей операции.

В префиксной форме алгоритм аналогичен (только читаем выражение не слева – направо, а справа налево)

Procedure Vch(a:string;Var pp:Boolean;Var z:integer);

Var head:ps;

I,k:integer;

R,w:integer;

Begin

Head:=nil;

pp:=true; //возможно вычислить

while (i<=length(a)) and pp do

begin

if a[i]<>’ ‘ then //игнорируем пробелы

begin

if not (a[i] in [‘+’,’-’,’*’]) then //если не операция

begin

val(a[i],r,k),

if k=0 then writeStack(head,r)

else pp:=false;

end

else

begin //если операция

if head<>nil then ReadStack(head,r)

else pp:=false;

if head<>nil then ReadStack(head,w)

else pp:=false;

if pp then

begin

case a[i] of

‘+’: r:=r+w;

‘-’: r:=r-w;

‘*’: r:=r*w;

End;

writeStack(head,r);

end;

end;

end;

inc(i);

end;

readStack(head,z);

end

8. Деревья, основные определения. Понятие бинарного дерева, Способы

прохождения дерева. Дерево - формула: построение, использование.

Дерево – связный граф без циклов. G = (N, M), где N – вершина, M – ребро.

Определение дерева:

1) Если G – связный граф и M = N-1.

2) G – ациклический и M = N-1. G – ациклический граф, облад. св-вом: если какую-либо пару несмежных вершин соединить ребром, то получаемый граф будет содержать ровно 1 цикл.

3) Любые 2 несовпадающих вершины графа G соединяет единственная простая цепь.

Корень дерева – единств. вершина, наход. вверху перевернутого дерева; листья – самые нижние вершины дерева; внутр. вершина – ни корень, ни лист; родитель (предок) – вершина, кот. наход. непосредственно над др. вершиной; потомок – вершина, которая находится непосред. под др. вершиной. Max уровень какой-либо вершины дерева – глубина (высота) дерева. Число потомков вершины – ее степень. Max значение этих степеней – степень дерева.

Бинарное дерево – дерево, степень которого равна 2. Каждая вершина, узел дерева, может иметь не более 2 потомков их называют левым и правым. Двоичное дерево считается идеально сбалансированным, если для каждой его вершины кол-во вершин в левом и правом поддеревьях различается не более чем на 1. Дерево явл. сбалансированным т и тт, когда для каждого узла высота его двух поддеревьев различается не более, чем на 1.

B-деревья представляют собой разновидность сбаланс. деревьев. Они относятся к классу сильно ветвящихся деревьев. Их особенность состоит в том, что в узле хранится не одно значение ключа, а несколько, и соответственно это кол-во ключей опр. кол-во потомков узла. Ключ каждого внутреннего узла окружен указателями. Указатели отсылают к ключам, которые либо все большие, либо все меньшие окруженного ключа. Определение B-дерева порядка n:

1. Каждая страница содержит не более 2n эл-тов (ключей)

2. Каждая страница кроме корневой, содержит не менее n эл-тов.

3. Каждая страница либо представляет собой лист (т.е. не имеет потомков), либо имеет m+1 потомка, где m – число ключей на данной странице.

4. Все страницы-листья находятся на 1 уровне.

B+ - деревья – данные хранятся только в листьях, во внутренних узлах хранятся только копии ключей, которые помогают искать новые листья. Указатель (левый) ведет к узлам, которые меньше заданного значения, а правый к тем, который больше или = заданным значениям. Эти деревья используются для организации каталогов файловой системы NTFS.

Описание вершины дерева поиска имеет вид:

Type pt=^nodl;

nodl=record

data: Integer;

left, right: pt;

end;

Основные операции:

- вставка элемента в дерево.

- обход дерева.

- удаление элемента из дерева.

Вставка эл-та, выполняемая с помощью рекурсивной процедуры.

procedure Ins_Tree (var t: pt; x: integer) //t очередная вершина, x – значение вставляемого эл-та

begin

if t=nil then begin

new(t)

with t^ do

begin

left:=nil; right:=nil;

data:=x;

end; end;

else

if x<=t^.data then Ins_Tree(t^.left,x) else Ins_Tree(t^.right,x)

Бинарное дерево – дерево, степень которого равна 2. Каждая вершина, узел дерева может иметь не более 2 потомков, их называют левым и правым.

Для работы с древовидными структурами имеется множество алгоритмов. Во всех алгоритмах встречается одна и та же идея – идея прохождения или обхода дерева. Это способ методичного исследования узлов дерева, при котором каждый узел проходится ровно 1 раз. Многие алгоритмы при использовании деревьев упрощаются. 3 способа прохождения дерева:

1) узлы можно проходить в прямом порядке – preorder (обход дерева в глубину);

2) в обратном порядке – postorder;

3) в концевом порядке.

Эти способы определяются рекурсивно. Прохождение выполняется в 3 этапа для каждого способа прямой порядок:

1) попасть в корень;

2) пройти левое поддерево (в прямом порядке);

3) пройти правое.

postorder: Л-К-П.

endorder: Л-П-К.

Л-К-П – инфиксный порядок;

Л-П-К – суффиксный (постфиксный) порядок;

К-Л-П – префиксный порядок.

Процедура обхода:

Procedure PrintTree(t:pt);

Begin

If t<>nil then

Begin

PrintTree(t^.left);

Memo1.lines.add(IntToStr(t^.data));

PrintTree(t^.right);

End;

End;

Бинарное дерево поиска — это структура данных, в которой данные хранятся в элементах структуры, напоминающей дерево. Каждый элемент может иметь не более двух "сыновей", поэтому дерево называется бинарным.

Каждый элемент имеет ключ — целое уникальное число. Дерево устроено так, что у любого элемента справа находятся все элементы с ключами больше чем его ключ, а слева — меньше. Благодаря этому в таком дереве осуществляется быстрый поиск, так как глубина дерева меньше числа элементов. Элементы "упорядочены" внутри дерева.

Для организации такой структуры достаточно реализовать три операции: 1) поиск элемента; 2) вставка элемента; 3) удаление элемента;

При поиске достаточно пройти от корня (самого первого элемента) по дереву, спускаясь вниз до искомого элемента, попутно сравнивая текущий элемент с искомым.

Операция вставки элемента немного напоминает операцию поиска. Достаточно пройти по дереву вниз, так как это происходит при поиске, пока мы не упремся в элемент, не имеющий сына с той стороны, куда мы должны были бы двинуться. Вставим новый элемент. Иногда мы не сможем добавить элемент, так как наше дерево будет слишком глубоким.

Удаление — самая сложная из операций. Сначала требуется найти удаляемый элемент. Если у него нет сыновей, то просто уберем его. Если у него один сын, то достаточно соединить его сына с его отцом "в обход" его самого. При удалении элемента с двумя сыновьями мы должны сначала найти элемент, следующий за ним в смысле порядка на ключах. Для этого найдем минимальный элемент в правом поддереве удаляемого элемента. Назовем его просто следующим. Теперь поменяем местами удаляемый элемент и следующий. После этого удаляемый элемент имеет не более одного сына и его можно легко удалить. Для нахождения следующего за удаляемым элемента достаточно найти минимальный элемент в правом поддереве удаляемого. Оно существует, ибо мы удаляем элемент с двумя сыновьями.