Задание к лабораторной работе

1. Изучить теоретическую часть.

2. Составить программу, которая по строке описания массива эмулирует его размещение в выделенном участке оперативной памяти. Входные данные вводятся с клавиатуры. Формат ввода выбрать самостоятельно. Реализовать следующие действия: ввод данных, вывод дескриптора, обращение к произвольному элементу массива (чтение и запись), обращение к произвольному байту выделенной памяти (чтение и запись), вывод сведений об авторе.

3. Используя построенный дескриптор, вычислить «вручную» адрес заданного слота по его индексам.

Контрольные вопросы и задания

1. Дайте определения следующим терминам и понятиям: массив, слот, линеаризация, вектор, матрица, последовательное расположение в памяти, прямое обращение по индексу, дескриптор.

2. Объясните назначение дескриптора и его составляющих.

3. Объясните, как выводится формула доступа.

4. Объясните, что такое нулевой слот.

5. Докажите формулы расчета адреса произвольного элемента для массива размерности n.

6. Выведите формулу расчета адреса нулевого слота для массива размерности n.

Рекомендуемая литература

1. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах.

2. Разумов О.С. Организация данных в вычислительных системах. М.: Статистика, 1978.

Лабораторная работа №4

СТЕК. ФОРМЫ ЗАПИСИ АРИФМЕТИЧЕСКИХ И ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ. ПРИМЕНЕНИЕ СТЕКА ДЛЯ КОМПИЛЯЦИИ ВЫРАЖЕНИЙ

Стек

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

В первом случае рост стека (добавление элементов) осуществляется за счет выделения свободных элементов памяти. Такая организация предполагает формирование связной структуры стека.

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

Операции, выполняемые над стеком, имеют специальные названия. При добавлении нового элемента мы говорим, что элемент помещается в стек (операция push). Для стека s и элемента i можно определить операцию push(s,i). Аналогично определяется операция выборки из стека pop(s), по которой из стека удаляется верхний элемент и возвращается в качестве значения функции.

Пример 1. Связный стек может быть организован как список:

TYPE elem = record { звено стека }

inf:type_elem; {с информационным полем inf}

ref:next {и полем ссылки ref на следующее звено}

end;

next = ^elem;

VAR top:next; {указатель на вершину стека}

Пример 2. При использовании массива стек может быть определен следующим образом:

CONST n=100; {максимальный размер стека}

VAR stack:array[1..n] of type_elem;

top: 0..n; {указатель на занятый элемент}

Система польской записи

Система польской записи алгебраических выражений обеспечивает определенные преимущества по сравнению с традиционной, так называемой инфиксной записью. Различие между системами состоит в порядке записи операндов и знаков операций. Классификация форм записи выражений приводится в следующей таблице.

Форма записи	Принцип записи	Пример
инфиксная (традиционная)	Операнд1 Операция Операнд2	a + b * (c – d) / e
префиксная (польская)	Операция Операнд1 Операнд2	+ a * b / – c d e
суффиксная (обратная польская)	Операнд1 Операнд2 Операция	a b c d – * e / +

Отметим, что выражения в префиксной и суффиксной формах являются бесскобочными.

Прямая и обратная польская запись это форма задания выражений, удобная для организации вычисления значения выражения. Сформулируем алгоритм для вычисления значения выражения, заданного в обратной польской записи.

п1. Найти в выражении знак крайней слева операции.

п2. Выбрать два операнда, стоящих непосредственно слева от найденной операции.

п3. Выполнить эту операцию.

п4. Заменить операнды и знак операции полученным результатом.

п5. Повторять вычисления с п1, до тех пор пока выражение не будет преобразовано в заключительный результат.

Пример. Рассмотрим выражение 5 + 8 / 2 * 3. Переведем его в обратную польскую запись: 5 8 2 / 3 * +. В соответствии с алгоритмом выражение будет преобразовываться следующим образом (подчеркнутым шрифтом в примере выделяется выполняемая операция):

5 8 2 / 3 * +  5 8 2 / 3 * +  5 4 3 * +  5 12 +  17

Сформулированный алгоритм рассчитан только на использование двухместных операций. Несложно обобщить правило записи выражений в обратной польской записи и их вычисления для случая использования многоместных операций (в том числе и одноместных).

Рассмотрим вопрос корректности выражений. Для этого введем понятие ранга для выражения в обратной польской записи.

Ранг любого операнда (константы или идентификатора) определим равным единице. Ранг операции равняется 1–n, где n количество операндов этой операции. Например, умножение – двухместная операция, поэтому ее ранг равен 1–2 = –1.

ТЕОРЕМА. Польская суффиксная формула корректна тогда и только тогда, когда ранг этой формулы равен 1, а ранг любой ее левой части больше либо равен 1.

Пример. Вычислить ранг формулы A B C / D * +. Проанализируем формулу в порядке слева направо, указывая под ней изменяющееся значение счетчика ранга:

Элементы формулы:		A	B	C	/	D	*	+
Значение счетчика ранга:	0	1	2	3	2	3	2	1

Следовательно, формула корректна.

Пример. Формула "A B C / + *" некорректна, так как ее ранг равен 0. Формула "A B C + + + D" некорректна, так как ранг ее левой части "A B C + + +" меньше 1.

Преобразование инфиксных выражений в обратную польскую запись

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

Элементы формулы	Приоритет	Ранг
Операции: +, –	1	1
Операции: *, /	2	1
Операнды	3	1
Маркер конца: #	0

Символ "#" будет использоваться нами одновременно как символ конца стека и входной (анализируемой) строки.

Для последующего алгоритма выберем следующие идентификаторы переменных:

R – ранг формулы;

Top – указатель на вершину стека;

S[Top] – элемент на вершине стека S;

P[i] – i ый символ выходной строки P;

NextChar– функция, возвращающая очередной символ входной строки;

N – анализируемый символ входной строки;

Pr(N) – функция, определяющая приоритет символа N входной строки;

T – символ (рабочая переменная);

Rang(T) – функция, определяющая ранг символа T.

Ниже приводится алгоритм преобразования инфиксного выражения в обратную польскую запись.

п1.{ Инициализация стека } Top:=1; S[Top]:= '#''

п2.{ Начальные значения переменных } R:=0; i:=0

п3.{ Выбор первого символа входной строки } N:=NextChar

п4.{ Просмотр входной строки } Повторять п5 и п6 пока N<>'#'

п5.{ Удаление символов с большим или равным приоритетом из стека в выходную строку } Повторять пока Pr(N)Pr(S[Top])

п5.1. i:=i+1

п5.2. T:=S[Top]; Top:=Top–1

п5.3. P[i]:=T

п5.4. R:=R+Rang(T)

п5.5. {контроль корректности}если R<1, то перейти к п9.

п6.{ Размещение в стеке символа N и определение следующего символа }

п6.1. Top:=Top+1

п6.2. S[Top]:=N

п6.3. N:=NextChar

п7.{ Удаление оставшихся элементов из стека } Повторять пока S[Top]'#'

п7.1. i:=i+1

п7.2. T:=S[Top]; Top:=Top–1

п7.3. P[i]:=T

п7.4. R:=R+Rang(T)

п7.5. если R<1, то перейти к п9.

п8.Если R1, то перейти к п9, иначе закончить работу.

п9.Печатать текст "Выражение некорректно".

Пример. Перевести инфиксное выражение «A+B–C*D/E*H» в обратную польскую запись. В следующей таблице приводятся изменяющиеся значения основных величин алгоритма.

Анали­зи­ру­е­мый символ (N)	Действие алгоритма	Содержи­мое стека (S)	Выход­ная строка (P)	Ранг (R)
	инициализация	#		0
A	добавление в стек	# A
+	выталкивание из стека и добавление в стек	# +	A	1
B	добавление в стек	# + B
–	выталкивание из стека и добавление нового символа	# –	AB+	1
C	добавление нового символа	# – C
*	выталкивание и добавление	# – *	AB+C	2
D	добавление нового символа	# – * D
/	выталкивание и добавление	# – /	AB+CD*	2
E	добавление нового символа	# – / E
*	выталкивание и добавление	# – *	AB + CD*E/	2
H	добавление нового символа	# – * H
#	выталкивание символов из стека	#	AB+CD*E/H*–	1

Преобразование инфиксного выражения, содержащего подвыражения в скобках

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

Упражнение. Преобразовать в обратную польскую запись выражение ((A+B)*C–D)/E.