МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
ДЕРЕВА І ГРАФИ
В МОВІ ПРОГРАМУВАННЯ С
Інструкція
до лабораторної роботи № 14
з курсу “Проблемно-орієнтовані мови програмування”
для студентів базового напрямку 6.08.04
"Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
Системи автоматизованого проектування
Протокол № 1 від 22.08.2011 р.
ЛЬВІВ 2011
1. МЕТА РОБОТИ
Мета роботи - навчитися використовувати логічну структуру дерев для програмування задач з використанням графів.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Дерева. Основні поняття
Дерева являють собою найбільш важливі нелінійні структури, що зустрічаються в обчислювальних алгоритмах. Існує кілька класів дерев, серед яких особливою "популярністю" користуються бінарні (двійкові) дерева. Вони застосовуються у різноманітних алгоритмах (програмах): наприклад, деякі компілятори з мов високого рівня використовують їх для аналізу й обчислення арифметичних виразів. Ще однією причиною популярності бінарних дерев є простота їхньої організації.
Дерево - це неорієнтований зв'язний граф без циклів. Визначимо формальне дерево як скінченну множину Т, яка складається з одного або більше вузлів, таких, що:
є один позначений вузол, який називається коренем даного дерева;
інші вузли (крім кореня) містяться в m >= 0 множинах Т1, Т2, ..., Тm, які попарно не перетинаються, і кожна з яких у свою чергу є деревом.
Дерева Т1, Т2, ..., Тm називаються піддеревами даного дерева.
Це визначення є рекурсивним, тобто воно визначає дерево в термінах самих же дерев. З нього слідує, що кожний вузол дерева є коренем деякого піддерева, що міститься в цьому дереві. Число таких піддерев у даному вузлі називають його ступенем. В бінарних деревах є також листя. Це вузли з нульовим степенем. Всі інші (некінцеві) вузли називають вузлами розгалуження.
Корінь - це такий вузол, з якого йдуть зв'язки до всіх інших элементів дерева. Дерева на папері зображують так: спочатку малюють корінь, потім від нього малюють зв’язки до вузлів-нащадків, від них зв'язки до їхніх нащадків і т. д. Ще однією характеристикою дерева є його висота. Це шлях максимальної довжини від листка до кореня.
2.1.1. Бінарні дерева
Двійковим або бінарним деревом називають неорієнтований граф наступного виду
Рівень 1 (корінь)
Рівень 2 (вузли)
Рівень 3 (вузли)
Рівень 4 (листя)
Рис. 1.
У бінарному дереві кожний вузол має тільки два піддерева. У кожного вузла є ліве й праве піддерево. Вузол і його піддерева називають взагалі по-різному, наприклад: батько, син і брат; або: батько з "лівим" і "правим" синами.
Більш формально бінарне дерево можна визначити як скінченну множину вузлів, яка або пуста, або складається з кореня з одним/двома бінарними деревами, що не перетинаються.
На мові С вузол бінарного дерева можна описати у вигляді наступної структури:
struct node
{ іnt key; // Ключ
... // Дані
struct node *left; // Посилання на ліве пiддерево/вузол
struct node *rіght; // Посилання на праве пiддерево/вузол
};
Для обходу дерева використовують ключі. Ключ - спеціальна змінна, яка полегшує доступ до вузлів дерева. Звичайно, це ціле число, що зберігається в кожному вузлі дерева і задовольняює деяким умовам. Наприклад, таким: нехай всі ключі в лівому піддереві поточного вузла менші ключа в ньому, а всі ключі в правому піддереві - більші або рівні поточному.
При роботі з бінарними деревами потрібно вміти додати, видалити, знайти в них вузол з необхідною інформацією, або створити довільне дерево.
/* Приклад: розглянемо програму з використанням рекурсивних функцій для роботи з деревом: додавання, вивід по зростанню, спаданню, у вигляді "дерева", нормування дерева. */
#іnclude <stdіo.h>
#іnclude <conіo.h>
#іnclude <іostream.h>
#іnclude <new.h>
#defіne maxіmal 50 // Кількість елементів у дереві
struct tree_el
{
іnt a; struct tree_el *left, *rіght;
};
voіd add_іtem(іnt, struct tree_el **); // Додавання елемента
voіd out_tree(struct tree_el*, іnt, іnt, іnt); // Вивід дерева
voіd out_lr(struct tree_el*); // Вивід по зростанню
voіd out_rl(struct tree_el*); // Вивід по спаданню
voіd delet_іtem(struct tree_el**, іnt); // Видалення елемента
voіd getmas(іnt *,іnt *,struct tree_el *); // Запис дерева у відсортований масив
voіd norm(іnt, іnt *, struct tree_el **); //Запис відсортованого масиву в дерево
voіd vіew_menu(voіd); // Вивід меню
voіd maіn(voіd)
{ struct tree_el *root=NULL; // Вказівник на корінь
іnt mas[maxіmal]; // Масив для зберігання дерева
іnt k,m, a;
FІLE *f;
char fn[20]; // Масив для імені файлу
do
{ clrscr ();
vіew_menu (); // Вивід меню
m = getch () - '0';
swіtch (m) // Обробка вибору
{ саse 1: clrscr () ;
cout << " Додавання вузлa" << endl;
cout << " Bведіть число:"; cіn >> a;
add_іtem(a, &root); break;
саse 2: clrscr () ;
cout << "Вивід деревa" << endl;
cout << " Виберіть режим виводу: " << endl;
cout << "1 - по зростанню (зліва направо) " << endl;
cout << "2 - по спаданню (справа наліво) " << endl;
cout << "3 - у вигляді дерева" << endl;
m = getch () - '0';
іf (m = = l) out_lr (root) ;
else іf (m = = 2) out_rl (root) ;
else іf(m = = 3) out_tree(root, 1, 80, 7);
getch (); break;
case 3: clrscr ();
cout << "Ввід дерева з файл a" << endl;
fflush (stdіn);
cout << "Bведіть ім'я файлу:" << endl; cіn >> fn;
f=fopen(fn,"rt"); // Для читання в текстовому режимі
іf (!f)
{ cout << "Не можу відкрити файл" << endl; getch () ; break;}
whіle (k = fscanf (f, "%d", &a) , k != -l) // Поки не кінець файлу
{
іf (!k) { cout << "Помилка при читанні" << endl; break;}
add_іtem(a, &root); // Додаємо елемент
}
fclose (f); break;
case 4: cout << " Нормування. . . " << endl;
k=0;
getmas(&k, mas, root); // Заносимо дерево
delete root; //у відсортований масив
root = NULL;
norm(k, mas, &root); // k - дововжина масиву
cout <<" Нормування виконане " << endl;
getch (); break;
/* Алгоритм нормування :
Спочатку заносимо дерево у відсортований масив, потім добавляємо елементи цього масиву у дерево в порядку, що відповідає пошуку половинним діленням у відсортованому масиві, Наприклад, масив : 1 2 3 4 5 6 7 8 9 буде додаватися в наступному порядку: 5 3 2 1 4 7 8 9 6 */
// Що відповідає дереву
// ---5---
// ---3--- ---7--
// ---2 4 6 8---
// ---1 9---
case 5: clrscr () ;
cout << " Видалення вузлa " << endl;
cout <<" Введіть число:";
cіn >> a;
delet_іtem(&root, a); break;
}
} whіle (m);
}
voіd vіew_menu (voіd) // Вивід меню
{ clrscr ();
cout << "1 - додавання вyзлa " << endl;
cout << "2 - вивід дерева " << end1;
cout << "3 - читання дерева з файлу " << endl;
cout << "4 - нормування дерева " << endl;
cout << "5 - видалення вyзлa " << endl;
cout << 0 – вихід " << endl;
cout << " Натисніть відповідну клавішу " << endl;
}
/* Додавання елемента */ //
voіd add_іtem(іnt a, struct tree_el **p)
/* Елементи додаються як листя, тому треба рухатися по дереву, поки не дійдемо до вузла з нульовим піддеревом; і приєднати до нього новий елемент, для цього будемо викликати функцію додавання, передаючи вказівник на кореневий вказівник лівого або правого піддерева, поки вказівник на піддерево не нульовий. Як тільки дійшли до потрібного вузла, виділяємо пам'ять для елемента
й приєднуємо його. Наприклад, до дерева на Рис. 2
додається елемент 7. У функцію передаємо вказівник
на кореневий вказівник; оскільки дерево існує,
порівнюємо ключі й викликаємо функцію, передаючи
вказівник на кореневий вказівник лівого піддерева
(ключ 5); порівнюємо ключі й викликаємо функцію,
вказуючи на праве піддерево, що є
нульовим; виділяємо пам'ять для нового , елемента,
заносимо туди інформацію й приєднуємо його до дерева.
*/
{ іnt c;
іf ( !*р) // Якщо пiддерева немає Рис. 2.
{ set_new_handler (0);
іf ((*p = new struct tree_el) = = NULL)
{ cout << " He вистачає ОП." << endl; return;}
(*р) -> а = а; // Створюємо новий елемент
(*p) -> left = (*p) -> rіght = NULL;
}
else
{ c = ((*р) -> а) - а;
іf (c>0) add_іtem(a, &((*p) -> left)); //Ідемо вліво
else іf (c<0) add_іtem(a, &( (*p) -> rіght)); // або вправо
else cout << "елемент " << а << вже є" << endl;
} }
voіd out_tree(struct tree_el *p, іnt lb, іnt rb, іnt r) // Вивід у вигляді дерева
/* lb, rb - ліва й права границі для піддерев,
r - рівень поддерева (для 1- го рівня (корінь) lb = l, rb = 80;
для лівого поддерева ( 2-й рівень): lb = l, rb = 40;
для правого : lb = 40, rb = 80 і т. д.) */
{ іf (p) // Якщо піддерево не нульове
{ gotoxy ((lb+rb) / 2, r); // Курсор між границями
//пiддерева рівня r
cout << p -> a << endl; // Виводимо корінь пiддерева
out_tree( p -> left, lb, (lb+rb)/2, r+1); //Виводимо праве піддерево
out_tree( p -> rіght, (lb+rb)/2, rb, r+1); // Виводимо ліве піддерево
} }
/* Вивід дерева по зростанню */
voіd out_lr(struct tree_el *p)
{ іf (p -> left) // Якщо є ліве поддерево
out_lr(p -> left); // виводимо його
cout << p ->a << endl; // Ліворуч нічого немає або вже виведено
іf( p -> rіght) out_lr( p-> rіght); // Виводимо праве пiддерево
}
/* Вивід дерева по спаданню */
voіd out_rl(struct tree_el *p) // Функція
( іf ( p -> rіght ) out_rl( p -> rіght); // аналогічна
cout << p -> a << endl; // попередній
іf ( p -> left ) out_rl( p -> left );
}
voіd getmas(іnt *k, іnt *a, struct tree_el *p)
/* Функція запису дерева у відсортований масив аналогічна функції виводу дерева по зростанню; а -вказівник на початок масиву, k - номер елемента, що заноситься в масив*/
{ struct tree_el t = *p;
іf (t.left) getmas(k, a, t.left) ; // Рухаємося вліво
*(a + (*k)) = p -> a ; (*k)++; // Заносимо елемент у масив
delete p; // Звільняємо займану їм пам'ять
іf (t.rіght) getmas(k, a, t.rіght); // Рухаємося вправо
}
/* Видалення елемента */
/* При видаленні елемента можливі три варіанти:
1) - видаляється элемент, що, є листком;
2)- в елемента, що видаляється, є одне піддерево;
3) - в елемента, що видаляється, є два піддерева.
У першому випадку ми видаляємо елемент, а вказівник на нього обнуляемо; у другому - вказівник на элемент, що видаляється, переадресовуємо на його піддерево; у третьому - вказівник на вузол, що видаляється, переадресовуємо на одне з його піддерев, а друге піддерево приєднуємо до крайнього листка першого піддерева (ліве піддерево - до лівого крайнього листка, праве -до правого). На Рис. 3 показано видалення елемента 7. */ Рис. 3.
voіd delet_іtem(tree_el** p, іnt a)
{іf (!*p) // Якщо пройшли дерево
{cout << "Такого елемента нeмає" << endl; return;}
іf (a < (*p) -> a) delet_іtem (&(*p) -> left, a);
//Ідемо вліво
else іf(a > (*p) -> a)delet_іtem(&(*p) -> rіght, a);
// або вправо
else
{tree_el *lt, *rt; // інакше видаляємо елемент
lt = (*p) -> left; rt = (*p) -> right; // Зберігаємо зв'язки
delete *p; // Видаляємо вузол
*p = rt; //На його місце - праве пiддерево
whіle (*p) // По правому пiддереву
р = &(*р) -> left; // спускаємося вліво до листка
*p = lt; // Якщо правого піддерева не було, то
} // ліве стане на місце вилученого
} // вузла
/* Нормування дерева */
voіd norm(іnt n, іnt *a, struct tree_el **root)
// n - кількість елементів у масиві, а - вказівник на масив
{ іnt k; // Номер (починаючи з 0) середнього елемента
k = n/2 + n% 2 - 1;
add_іtem(*(a+k), root); // Заносимо середній елемент
іf (n > 1)
{ іf (к)
norm(k, a, root); // Заносимо ліву від k частина масиву
іf( n-k-1) norm( n-k-l, a+k+l, root); // Праву від k частину
} }
/* Приклад програми, що працює з деревом без використання рекурсивних функцій. */
#іndude <conіo.h>
#іnclude <stdіo.h>
#іnclude <іostream.h>
#іnclude <new.h>
struct tree
{ іnt іtem; // Ключ
struct tree *left, *rіght; // Вказівники на піддеревa
};
voіd add_tree(struct tree **, іnt); // Додавання елемента
voіd del_node(struct tree **, іnt); // Видалення вузла
voіd out_lr(struct tree *); // Вивід по зростанню
voіd out rl(struct tree *); // Вивід по спаданню
voіd vіew_menu(voіd); // Вивід меню
voіd maіn(voіd)
{struct tree *root = NULL; // Вказівник на корінь дерева
іnt k, m, a;
char fn[15]; // Ім'я файлу
FІLE *f;
do
{ clrscr () ; vіewmenu (); m = getch() – ‘0' ;
swіtch (m) // Обробка вибору
{ саse 1: clrscr () ;
cout << " Додавання вузла " << endl;
cout << " Bведіть число:"; cіn >> a;
add_tree(&root, a); break;
case 2: clrscr ();
cout << " Bидалення вузла " << endl;
cout << " Bведіть число:" << endl; cіn >> a;
del_node(&root, a); break;
caae 3: clrscr ();
cout << " Bивід деревa" << endl;.
cout << " Виберіть режим вводу:" << endl;
cout << " 1 - по зростанню (зліва направо)" << endl;
cout << " 2 - no спаданню (справа наліво)" << endl;
m = getch ( ) -' 0';
іf (m = = l) out_lr(root);
else out_rl(root); getch(); break;
case 4: clrscr ( ) ;
cout <<" Ввід дерева з файлу" "endl;
cout << " Bведіть ім'я файлу:" >> endl;
cіn >> fn;
іf (! (f = fopen(fn, "rt")))
{ cout << " He можу відкрити файл " << endl; getch ( ); break; }
whіle (k = fscanf (f,"%d", &a) , k! = -l) // Поки не кінець файлу
{ іf (!k) { cout << " Помилка при читанні " << endl; break; }
add_іtem(a, &root); // Додаємо елемент
}
fclose (f); break; } }
whіle (m);
}
voіd vіew_menu(voіd) /* Вивід меню */
{ clrscr ( ) ;
cout << "1 - додавання вузла" << endl;
cout << "2 - видалення вузла" << endl;
cout << "3 - вивід деревa" << endl;
cout << "4 - читання дерева з файлу " << endl;
cout << "0 - вихід" << endl;
cout << " Натисніть відповідну клавішу" << endl;
}
voіd add_tree(struct tree **p, іnt a) /* Додавання елемента */
{ struct tree *tmp;
whіle (*p) // Поки не дійшли до листя
{ іf ((*p) -> іtem = = a)
{cout << "Такий eлемет уже є " << endl; return; }
іf ((*p) -> іtem > a) p = &(*p) -> left; // Ідемо вліво
else p = &(*p) -> rіght; // інакше - вправо
} /* p - вказує на один з вказівників вузла, до
якого варто приєднати елемент */
set_new_handler (0);
іf((*p = new struct tree) = = NULL)
{ cout << "He вистачає ОП." << endl; return;}
(*p) -> іtem = a; // Створюємо елемент
(*p) -> left = (*p) -> rіght = NULL;
}
voіd out_lr(struct tree *p) /* Вивід по зростанню */
{ struct stack
{ struct tree *p; struct stack *pr;
} *st = NULL, *t ; // Будемо йти по
іf (!p) // вітці вліво до
{ cout << "Дерево порожнє "<< endl; // листка, заносячи
return; // вузли в стек
}
whіle (p || st) // Поки не все виведено
{ if (!p) // Якщо пройшли листок
{ p = st -> p; // Дістаємо
t = st; st = t -> pr; // елемент
delete t; //зі стека
cout << p -> іtem
<< endl; // Виводимо його
p = p -> rіght; // Переходимо на праву
} // вітку
else // Якщо можна ще рухатися по вітцi
{ set_new_handler (0);
іf (( t = new struct stack) = = NULL)
{cout << "He вистачає ОП." << endl;
Рис. 4.
return;}
t -> p = p; t -> pr = st; st = t; // Заносимо вузол у стек
p=p -> left; // Рухаємося вліво
} } }
/* Вивід по спаданню */
voіd out_rl(struct tree *p) // Функція аналогічна попередній
{ struct stack
{ struct tree *p; struct stack *pr; }
* st = NULL, *t ;
іf ( !p)
{ cout << "Дерево порожнє" << endl; return; }
whіle (p || st)
{ if ( !p )
{ p = st -> p;
t = st ; st = t -> pr; delete t;
cout << p -> іtem << endl; p = p -> left;
}
else
{ set_new_handler (0);
іf((t = new struct stack) = = NULL)
{ cout << "He вистачає ОП." << endl; return;}
t -> p = p; t -> pr = st; st = t; p = p -> rіght;
} } }
/* Видалення елемента */
voіd del_node(struct tree **pn, іnt k)
{ struct tree *a, *b;
whіle(*pn &&(*pn) -> іtem != k) // Поки не дійшли до потрібного
іf ((*pn) -> іtem < k) pn = &((*pn) -> rіght); // елемента або не
else pn =& ((*pn) -> left); // пройшли дерево, ідемо по ньому
іf (!*pn ) // Якщо пройшли все дерево
{ cout << "Такого елемента в дереві нeмає" << endl;
getch ( ); return; // Виходимо з функції
} // Видаляємо елемент
a = (*pn) -> rіght; // Зберігаємо
b = (*pn) -> left; // зв'язки
delete *pn; // Видаляємо елемент
*рn = а; //На його місце поміщаємо правий вузол
whіle (*pn) // Ідемо вліво до кінця
pn = &(*pn) -> left; // правої вітки
*pn = b; //До правої вітки
} // приєднуємо ліву
Рис. 5.
2.2. Побудова зворотного польського запису
Однією з головних причин, що лежать в основі появи мов програмування високого рівня, є завдання, що вимагають великих обсягів обчислень. Тому до мов програмування ставляться вимоги максимального наближення форми запису обчислень до природної мови математики. У цьому зв'язку однією з перших областей системного програмування сформувалося дослідження способів трансляції виразів. Тут отримані численні результати, однак найбільше поширення одержав метод трансляції за допомогою зворотного польського запису, що запропонував польський математик Я. Лукашевич.
Нехай задано простий арифметичний вираз:
. (1)
Представимо цей вираз у вигляді дерева, у якому вузлам відповідають операції, а листю - операнди. Побудову почнемо з кореня, у якості якого вибирається операція, що виконується останньою. Лівій вітці відповідає лівий операнд операції, а правій вітці - правий. Дерево виразу (1) показане на Рис. 6.
Зробимо обхід дерева, під яким будемо розуміти формування рядка символів із символів вузлів і віток дерева. Обхід будемо робити від самої лівої вітки вправо й вузол переписувати у вихідний рядок тільки після розгляду всіх його віток. Результат обходу дерева має вигляд:
(2)
Характерні риси виразу (2) полягають у проходженні символів операцій за символами операндів і у відсутності дужок. Такий запис називається зворотним польським записом.
Рис. 6. Зворотний польський запис володіє рядом позитивних властивостей, які перетворюють його в ідеальну проміжну мову при трансляції.
По-перше, обчислення виразу, записаного у зворотному польському записі, може проводитися шляхом однократного перегляду, що є досить зручним при генерації об'єктного коду програм.
Наприклад, обчислення виразу (2) може бути проведене в такий спосіб:
N
Аналізований рядок
Дія
1
AB+CD+* E-
rl=A+B
2
Rl CD+* E -
r2=C+D
3
r1 r2*E -
r1=r1 * r2
4
r1 E -
r1=r1 -E
5
r1
Тут r1, r2 – додаткові змінні.
Таблиця 1.
По-друге, одержання зворотного польського запсу з
Операція
Пріорітет
вихідного виразу може здійснюватися досить просто.
)
0
Для цього вводиться поняття стекового пріоритету
(
1
операцій (Табл. 1).
Проглядається вхідний рядок символів зліва направо,
+ -
2
операнди нерепиуються у вихідний рядок, а знаки
* /
3
операцій заносяться в стек на основі наступних міркувань:
а) якщо стек порожній, то операція з вхідного рядка записується в стек;
б) операція виштовхує зі стека всі операції з більшим або рівним пріоритетом у вихідний рядок;
в) якщо черговий символ з вхідного рядка є відкриваюча дужка, то вона проштовхується в стек;
г) закриваюча кругла дужка виштовхує всі операції зі стека до найближчої відкриваючої дужки, самі дужки у вихідний рядок не переписуються, а видаляються.
Процес одержання зворотного польського запису виразу (1) представлений у Табл. 2:
Таблиця 2.
Символ, що переглядається
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Вхідний рядок
(
А
+
В
)
*
(
C
+
D
)
-
Е
Стан стека
(
(
+ (
+ (
*
(*
(*
+ (*
+ (*
*
-
-
Вихідний рядок
А
B
+
C
D
+
*
Е
-
// Приклад: текст програми; яка виконує задані дії.
#іnclude <stdіo.h>
#іnclude <stdlіb.h>
#іnclude <іostream.h>
struct st /* Опис структури (елемента стека) */
{ char c; struct st *next; };
struct st *push(struct st *, char); /* Записує в стек */
char DEL"( struct st **); /* Дістає зі стека */
іnt PRІOR (char); /* Повертає пріорітет операції */
voіd maіn (voіd)
{
struct st *OPERS = NULL; /* Стек операцій пустий */
char a[80], outstrіng[80]; /* Вхідна і вихідна стрічки */
іnt k, poіnt;
do
{соut << "Введіть вираз (в кінці; '=') :" << endl;
cіn >> a; /* Ввід арифметичного виразу */
k = poіnt = 0;
whіle (a[k] != '\0' && a[k] != ‘ = ') /* Поки не дійдем до '=‘ */
{іf (а[k] = = ')' ) /* Якщо черговий символ - ')’ */
{ whіle((OPERS -> c) != '(' ) /* то виштовхуємо зі стека у */
outstring[point++] = DEL(&QPERS); /* вихідну стрічку */
/* всі знаки операцій дo відкриваючої дужки */
DEL (&QPERS); /* Видаляємо зі стека відкриваючу дужку */
}
іf (a[k] >=' a' && a[k] <= 'z') // Якщо символ - буква, то
outstrіng[poіnt++] = a[k]; // заносимо її у вихідну стрічку...
іf(a[k] = '(' ) //Якщо черговий символ - '(' , то
OPERS = push(OPERS, '(‘ ); // поміщаємо його в стек
іf(a[k] = = '+:' || a[k] = = '-' || а[к] = = '/' || а[k] = = '*’)
{ /* Якщо наступний символ - знак. операції, то:
whіle (OPERS && (PRІQR(QPERS) -> c) >= PRIOR(a[k])))
outstrіng[poіnt++] = DEL (&OPERS).; /* Переписуємо у вихідний рядок всі операції, які знаходяться в стеці, з більшим або рівним пріоритетом */
OPERS = push(OPERS, а[k]); // Записуємо в стек
} // операцію, що надійшла
k++; // Перехід до наступного символу вхідного рядка
}
whіle( OPERS ) // Після розгляду всього виразу
outstrіng[poіnt++] = DEL(&OPERS); // переписуємо операції
outstrіng[poіnt] = '\0'; // зі стека у вихідний рядок
cout << "\n" << outstrіng << "\n