Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Застосування АТД
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2018
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
про виконання лабораторної роботи № 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); // конструктор з параметрами
~InfixToPostfix(); // деструктор
void AddInfixString(const string &str); // додавання інфіксного рядка
string TranslateToPostfix(); // перевід рядка з інфіксної до постфіксної форми запису
};
#endif /* _INFIX_TO_POSTFIX_H_ */
infix_to_postfix.cpp
#include "infix_to_postfix.h"
InfixToPostfix::InfixToPostfix() // конструктор за замовчуванням
{
}
InfixToPostfix::InfixToPostfix(const string &str) // конструктор з параметрами
{
input = str; // копіюєм вхідний рядок
}
InfixToPostfix::~InfixToPostfix() // деструктор
{
}
bool InfixToPostfix::isOperator(const char ch) const
{
if (ch == '+' || ch == '-' || ch == '*' || ch == '/') // якщо вхідний символ оператор
return true;
else // іншому випадку
return false;
}
int InfixToPostfix::GetPriority(const char ch) const
{
if (ch == '+' || ch == '-')
return 2;
if (ch == '*' || ch == '/')
return 3;
else
return 0;
}
void InfixToPostfix::AddInfixString(const string &str)
{
input = str; // копіюєм вхідний рядок
return;
}
string InfixToPostfix::TranslateToPostfix()
{
string output; // об"єкт вихідного рядка
for (unsigned i = 0; i < input.size(); ++i) // прохід по всьому вхідному рядку
{
if (isOperator(input[i])) // якщо це оператор
{
if (st.empty()) // якщо стек пустий
st.push(input[i]); // записуєм його в стек
else // в іншому випадку
{
if (GetPriority(st.top()) < GetPriority(input[i])) // якщо пріорітет символу > за пріорітет вершини стеку
st.push(input[i]); // додаєм оператор в стек
else // в іншому випадку
{
while ((!st.empty()) && (GetPriority(input[i]) <= GetPriority(st.top()))) // доки не знайдеться символ з меншим пріорітетом
{
output += st.top(); // додаєм вершину стеку в вихідний рядок
st.pop(); // видаляєм елемент зі стеку
}
st.push(input[i]); // записуєм оператор з вхідного рядка
}
}
}
else // в іншому випадку (якщо не оператор)
{
output += input[i]; // додаєм в вихідний рядок символ
}
}
while (!st.empty()) // доки стек не порожній
{
output += st.top(); // додаєм в вихідний рядок вершину
st.pop(); // вилучаєм елемент
}
return output; // повертаєм вихідний рядок
}
main.cpp
#include "infix_to_postfix.h"
#include <iostream>
using namespace std;
int main()
{
setlocale(0, "Ukr");
InfixToPostfix obj;
string str_inf, str_postf;
cout << "Enter infix string:" << endl;
getline(cin, str_inf); // зчитування інфіксного рядка
obj.AddInfixString(str_inf); // запис інфіксного рядка в клас InfixToPostfix
str_postf = obj.TranslateToPostfix(); // переведення інфіксного рядка в постфіксний
cout << endl;
// вивід результату
cout << "Result:" << endl;
cout << str_inf << " = " << str_postf << endl;
system("pause");
return 0;
}
Результат виконання програми:
/
Висновок:
На цій лабораторній роботі я ознайомився з АТД «СТЕК» .
03.04.2018 21:55
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора