Арифметические выражения

При описании арифметических выражений рекурсия означает возможность вложенности, т.е. использование в выражениях в качестве операндов подвыражений, заключенных в круглые скобки. Синтаксис языков программирования принято описывать с помощью рекурсивной нотации, называемой формой Бэкуса-Наура (БНФ). Она состоит из правил подстановки, определяющих как нетерминальный символ (т.е. символ, требующий дальнейшего уточнения) может быть замещен другим нетерминальным или терминальным символом (т.е. символом, не требующим уточнения). В правилах подстановки используется знак “|” для разделения альтернативных подстановок. Нетерминальные символы заключаются в угловые скобки “<>”. Символ “::=” означает “это есть”.

Определение простейшего арифметического выражения с помощью БНФ выглядит следующим образом:

<арифметическое выражение>::= < операнд> <знак операции> < операнд>

<операнд>:: = <идентификатор> | (<арифметическое выражение>)

<знак операции>:: = + | - | * | /

<идентификатор>:: = a | b | …| z | A | B | … | Z

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

Примеры простейших арифметических выражений, соответствующих данному определению: X+Y X * (Y + Z) (Y * Z) – X (X + Y) * (Z – W)

(X / (Y + Z)) * W и т.п.

6.3.2. Динамические линейные структуры данных: списки

Рекурсивное определение списка: список - это пустая структура или структура, состоящая из особого элемента (первого или головного) и списка. Рекурсивную интерпретацию линейного односвязного списка иллюстрирует рис. 61.

Рис. 61. Рекурсивная интерпретация списка

Как следует из рекурсивного определения списка, условием завершения его обработки является достижение пустого списка в процессе применения шагов рекурсии.

Рассмотрим две рекурсивные процедуры, одна из которых распечатывает содержимое информационных полей линейного односвязного списка в прямом порядке (Print_Front), а вторая – в обратном порядке (Print_Back).

Procedure Print_Front(first: PList);	{ распечатка содержимого списка }
Begin	{ в прямом направлении }
If first <> nil then begin
writeln(first^.info);
Print_Front(first^.link)	{ задняя рекурсия (см. ниже) }
end;
end;

Procedure Print_Back(first: PList);	{ распечатка содержимого списка }
begin	{ в обратном направлении }
if first <> nil then begin
Print_Back(first^.link)
writeln(first^.info);
end;
End;

6.3.3. Иерархические линейные структуры данных: наборы

Набор - это ортогональная структура иерархически определенных линейных списков. Набор - это линейная упорядоченная динамическая последовательность, каждый элемент которой является либо атомом, либо набором. Атом определяет “неделимый” элемент набора, предназначенный для хранения элементарной порции информации.

Пример структуры набора представлен на рис. 62:

Описание набора:

S{ 5 } = < 10, 20, R, 30, 40 >;

Эта запись означает, что набор, идентифицируемый указателем S, состоит из пяти элементов: атомов, содержащих значения 10 и 20, набора, идентифицируемого указателем R, и атомов, содержащих значения 30 и 40. Аналогично описаны наборы R и T.

R{ 3 } = < 50, T, 60 >;

T{ 3 } = < 75, 80, 90 >;

Рис. 62. Структура набора

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

Создать Т{ 3 } = < 75, 80, 90 >;

Создать R{ 2 } = < 50, 60 >;

Создать S{ 4 } = < 10, 20, 30, 40 >;

Первая директива означает, что необходимо создать набор, идентифицируемый указателем Т и состоящий из трех атомов со значениями 75, 80, 90. Остальные директивы определяются аналогично.

Включить Т в R{ 2 };

Включить R в S{ 3 };

Первая директива означает, что набор Т включается в набор R в качестве второго элемента. Вторая директива означает, что набор R включается в набор S в качестве третьего элемента. Результатом выполнения данных директив является структура набора, показанного на рис. 62.

Описание элемента хранения набора и процедура, распечатывающая значения атомов набора, приведены ниже.

Type
PNabor = ^ Nabor;	{ тип – указатель на элемент хранения набора }
Nabor = record	{ тип – элемент хранения набора }
right: PNabor;	{ горизонтальная связь в наборе }
case t: boolean of	{ признак типа элемента набора: }
true: (under: PNabor);	{ набор – вертикальная связь в наборе }
false: (zn: word)	{ атом – значение атома }
end;
Var Head: PNabor;
Procedure Write_Nabor(p: PNabor);	{ p – указатель на головной элемент набора }
begin
if p <> nil then begin	{ набор не пуст? }
if p^.t then Write_Nabor(p^.under)	{ элемент – набор: распечатать набор }
else writeln(p^.zn);	{ элемент – атом: распечатать значение атома}
Write_Nabor(p^.right)	{ распечатать следующий элемент набора }
end
end;

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