void View ( Tree *t, int level ) {
if ( t ) {
View ( t -> Right , level+1);	// Вывод правого поддерева
for ( int i=0; i<level; i++) printf("	");
printf(“ %d\n”, t -> info);
View( t -> Left , level+1);	// Вывод левого поддерева
}
}

Обращение к функции View будет иметь вид View(Root, 0);

переменная, определяющая, на каком уровне (level) находится узелР. Корень находится на уровне «0». Значения узлов выводятся по горизонтали так, что корень находится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла.

Функция View рекурсивная, вторым ее параметром является

Если закомментировать цикл

печати

пробелов, значения

ключей

будут

выведены просто в столбик.

И

Для последовательно введенных ключей 10 (кореньУ), 25, 20, 6, 21, 8, 1,

Г

Б

30, будет построено дерево, вывод которого на экран с помощью функции

View будет иметь следующий вид:

а

к

е

т

о

15.5.8. Освобожден е памяти

и

памяти,

занятой элементами

дерева,

может

Функция освобождения

быть реа

л

зована аналогично рекурсивной функции View

void Del

All(Treeб*t)

{

if ( t != NULL)

{

ли

Б

Del_All ( t -> Left);

Del_All ( t -> Right);

free(t);

}

}

15.6. Построение обратной польской записи

151

Сложные вычислительные задачи обычно требуют больших объемов

вычислений, поэтому к разработчикам языков программирования было

предъявлено требование: максимально приблизить форму записи

математических выражений в коде программы к естественному языку

математики.

Одну из первых областей системного программирования составили

исследования способов трансляции математических выражений.

В результате наибольшее распространение получил метод трансляции

при помощи обратной польской записи, которую предложил польский

математик Я. Лукашевич.

Рассмотрим алгоритмы получения обратной польской записи с

использованием структур в виде дерева и стека.

Р

15.6.1. Алгоритм, использующий дерево

Данный

алгоритм

основан

на

представлении

математического

И

выражения в виде дерева и использовании третьего способа его обхода (см. п.

15.5.6). Напомним его на примере арифметическогоУ

выражения

(A+B)*(C+D)–E.

Г

Представим это выражение в виде дерева, в котором узлам

соответствуют операции,

а листьям – опер нды. Построение начинается с

Б

корня, в качестве которого выбирается последняя выполняемая операция.

Левой

ветви соответствует л вый

опер нд операции, а правой ветви –

правый. Дерево выражения им

т вид:

а

к

Корень (уров нь 0)

-

У

вень 1-йе

т

*

E

Уровень 2-й

ро

+

+

и

A

B

C

D

л

Совершим

обход

дерева, под которым понимается формирование

стро

б

з с мволов узлов и ветвей дерева. Обход будем совершать от самой

левойкиветви вправо и узел переписывать в выходную строку только после

рассмотрения всех его ветвей. Обход совершаем строго по уровням:

Б

АВ+CD+

1) уровень 2:

2) поднялись на уровень 1:

*Е

3) и, наконец, корень:

–

В результате такого обхода получили обратную польскую запись:

AB+CD+*E–

(15.1)

152

15.6.2. Алгоритм, использующий стек

Получение обратной польской записи с использованием стека может осуществляться весьма просто на основе алгоритма, предложенного Дейкстрой, который ввел понятие стекового приоритета операций:

Операция		Приоритет
(	–	1
+		2
*	/	3

Суть алгоритма в следующем. Просматривается исходная строка символов S слева направо, операнды переписываются в выходную строку В, а

также извлекаем из стека; обе скобки (открывающая и закрывающая)

знаки операций заносятся в стек, который первоначально пуст, на основе
следующих правил:				Р
1) если в строке S встретился операнд, то помещаем его в строку В;
			И
2) если в S встретилась открывающая скобка, то помещаем ее в стек;
3) если в S встретилась закрывающая скобка, то выталкиваем из стека в
		У
строку В все операции до открывающей скобки, саму отрывающую скобку
	Г
	Б

игнорируются;
4) если в S встретилась операция Х, то выталкиваем из стека все
				к
операции, приоритет которых не ниже Х, после чего операцию Х записываем
в стек;			е		а
5) при достижении конца стро и S,					сли стек не пуст, переписываем его
		т
элементы в выходную строку В.
Обратная польская запись обладает рядом замечательных свойств,
	о
которые превращают ее в идеальный промежуточный язык при трансляции.
	и
Во-первых, выч сление выражения, записанного в обратной польской

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

Например, выч сление полученного выражения (15.1) может быть

проведено с едующим образом:
		л
	б		Шаг		Анализируемая строка	Действие
				1	AB+CD+*E–	R1=A+B
и
				2	R1CD+*E–	R2=C+D
				3	R1 R2*E–	R1=R1*R2
Б
				4	R1 E–	R1=R1–E
				5	R1

Здесь R1 и R2 – вспомогательные переменные.

153

15.6.3. Пример реализации

Пусть задано выражение a+b*c+(d*e+f)*g. Необходимо записать это выражение в постфиксной форме. Правильным ответом будет выражение abc*+de*f+g*+. Решаем эту задачу, используя стек.

Пусть исходная информация хранится в строке S=”a+b*c+(d*e+f)*g”. Результат будем получать в строке В.

Начинаем последовательно просматривать символы исходной строки, причем стек пуст и В – пустая строка.

Букву «a» помещается в строку В, а операцию «+» помещаем в стек. Букву «b» помещаем в строку В. На этот момент стек и строка В выглядят

более низкий приоритет. Букву «с» помещаем в строку В, после чего имеем

следующим образом:					Р
		В = ”ab”
				И
	+
Операцию «*» помещаем в стек, т.к. элемент в вершине стека имеет
			У
			Г

В = ”Бabс”

*

+

Следующий символ строки S «+». Ан лизируем стек и видим, что элемент в вершине стека «*» и следующий ним «+» имеют приоритеты не

ниже текущего, следовательно, о опер ции извлекаем из стека и помещаем
									за
в строку В, а текущий элемент пом ща м в стек. В итоге имеем
								к
									В = ”abс*+”
						+
						бе
Далее в строке S сл ду						символ «(», его помещаем в стек, а букву «d»
помещаем в строку В, в результате получается
					ет
				о					В = ”abс*+d”
						(
			и
						+
Следующий в строке S символ «*». Так как открывающую скобку
		л
нельзя звлечь из стека до тех пор, пока не встретилась закрывающая, то «*»
помещаем в стек. Букву «e» помещаем в строку В:
	б
и								В = ”abс*+de”
						*
Б
						(
						+

Следующий прочитанный символ «+», и т.к. элемент стека «*» имеет более высокий приоритет, то извлекаем его из стека и помещаем в строку В, а текущий символ «+» помещаем в стек. Символ «f» помещаем в строку В:

В = ”abс*+de*f”

+

(

+

154

Далее в строке S идет закрывающая скобка, все элементы стека до символа «)» помещаем в строку В (это элемент «+»), а сам символ «(» извлекаем из стека. Обе скобки игнорируются:

В = ”abс*+de*f+”

+

Операцию «*» помещаем в стек, а букву «g» – в строку В:

В = ”abс*+de*f+g”

*

+

Р

Все символы строки S рассмотрены,

следовательно, анализируем

И

состояние стека, если он не пуст, то переписываем все его элементы в строку

В:

У

В = ”abс*+de*f+g*+”

Таким образом, просмотрев исходную информацию только один раз,

мы решили поставленную задачу.

Текст программы, реализующий рассмотренный алгоритм, может

иметь следующий вид:

Г

. . .

а

struct Stack {

Б

char c;

// Символ опер ции

} ;

Stack *Next;

к

int Prior (char);

Stack* InS( Stack*,char);

е

Stack* OutS( Stack*,char*);

void main ()

{

и

// Стек операций Op – пуст

Stack *t, *Op = NULL;т

л

char a, In[50], Out[50];о

// Входная In и выходная Out строки

int k = 0, l = 0;

// Текущие индексы для строк

puts(" Input formula : "); gets(In);

// Анализируем символы строки In

while ( In[k] != '\0') {

и

// Если с мвол «)», выталкиваем из стека в выходную строку все операции

Б

бif ( In[k] == ')' ) {

while ( (Op -> c) != '(' ) {

// до открывающей скобки

Op = OutS(Op,&a);

// Считываем элемент из стека

if ( !Op ) a = '\0';

// и записываем в строку Out.

Out[l++] = a;

}

t = Op;

// Удаляем из стека открывающую скобку

Op = Op -> Next;

}

free(t);

// Если символ строки In – буква, заносим ее в строку Out

155

if ( In[k] >= 'a' && In[k] <= 'z' ) Out[l++] = In[k]; // Если символ – открывающая скобка, записываем ее в стек

if ( In[k] == '(' ) Op = InS(Op,In[k]);

/* Если символ – знак операции, переписываем из стека в строку Out все

операции с большим или равным приоритетом */

if ( In[k] == '+' || In[k] == '–' || In[k] == '*' || In[k] == '/' ) {

while ( Op != NULL && Prior (Op -> c) >= Prior (In[k]) ) {

Op = OutS(Op,&a);

// Извлекаем из стека символ

Out[l++] = a;

Р

}

И

}

Op = InS(Op,In[k]);

// Текущий символ – в стек

У

k++;

}

// Конец цикла анализа входной строки

// Если стек не пуст, переписываем все операции в выходную строку

while ( Op !=NULL) {

Г

Op = OutS(Op,&a);

}

Out[l++] = a;

а

Б

Out[l] = '\0’;

к

printf("\n Polish = %s", Out);

// Выводим на экран результат

}

е

//======= Функция реализации приоритета операций =========

int Prior ( char a ) {

switch ( a ) {

о

case '*':

case '/':

return 3;

}

case '–':

case '+':

return 2;

и

}

case '(': returnт1;

л

return 0;

б

// ============== Добавление элемента в стек =============

Stack* InS( Stack *t, char s) {

Stack *t1 = (Stack*) malloc(sizeof(Stack));

Б

= s;

t1 -> c

иt1-> Next = t;

return t1;

}

// ============== Извлечение элемента из стека ===============

Stack* OutS( Stack *t, char *s ) { Stack *t1 = t;

*s = t -> c; t = t->Next; free(t1); return t;

156