Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт про виконання лабораторної роботи № 2 з дисципліни: “Обчислювальний практикум” на тему: “ Застосування АТД "СТЕК" до розв’язання прикладних задач”  Львів 2013 Мета: Ознайомитись з АТД «СТЕК» Теоретичні відомості: Стек в програмуванні - різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім. Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї) Операції зі стеком push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow) pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow) Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку. Додаткові операції (присутні не у всіх реалізаціях стеку): isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній. isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе. clear: звільнити стек (видалити усі елементи). top: отримати верхній елемент (без виштовхування). size: отримати розмір (кількість елементів) стека. swap: поміняти два верхніх елементи місцями. Організація в пам'яті комп'ютера Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку. Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті. Приклади застосування Калькулятори, які використовують зворотну польську нотацію, використовують стек для збереження даних обчислень. Існують «стеко-орієнтовані» мови програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо). Стеко-орієнтованими є деякі з віртуальних машин, наприклад віртуальна машина Java. Компілятори мов програмування використовують стек для передавання параметрів в процесі виклику підпрограм, процедур та функцій. Спеціалізований стек використовується також для збереження адрес повернення з підпрограм. Варіант 2 Завдання: Перетворити вираз з інфіксної форми запису без дужок в постфіксну форму. Код програми: infix_to_postfix.h #ifndef _INFIX_TO_POSTFIX_H_ #define _INFIX_TO_POSTFIX_H_ #include <stack> #include <string> using std::string; // включення типу string з простору імен std; using std::stack; class InfixToPostfix { private: string input; // зберігає вхідний інфіксний рядок stack<char> st; // об"єкт типу Stack bool isOperator(const char ch) const; // визначає чи заданий символ оператор int GetPriority(const char ch) const; // повертає пріорітет заданого символа public: InfixToPostfix(); // конструктор за замовчуванням InfixToPostfix(const string &str); // конструктор з параметрами ~Infi...