Skip to content

Latest commit

 

History

History
84 lines (68 loc) · 8.07 KB

assignment_1.md

File metadata and controls

84 lines (68 loc) · 8.07 KB
Raw
Практична робота №1

Стеки, черги та калькулятор

Мета роботи:

Попрактикуватись у використанні створених самостійно структур даних (в цьому випадку - стеку), реалізувати програму, що обчислює арифметичний вираз

Завдання

Створіть програму, що приймає на вхід арифметичний вираз, що складається з чисел, дужок, та операторів +,-,*,/ та виводить результат обчислення на екран. Ви можете реалізувати як зчитування виразу з інпуту, так і з аргументів командного рядка.

Наприклад (> - введення в программу, < - вивід з програми):

> 2 * (3 + 7 - 1)
< 18

Як виконувати

Фактично, виконання данної роботи складається з трьох частин:

1. Розбиття на токени

Токени - рядки, значення яких можна певним чином класифікувати, та з якими ми зможемо працювати в наступних пунктах. Наприклад, 123, 5 та 999 - токени, що містять числа, а + та - - операції. В нашому випадку токенами можуть бути числа, знаки операцій або дужки. Наприклад, рядок 123* (3+10) розбивається на токени 123, *, (, 3, +, 10 та ). Процес розбиття рядка на токени називається токенізацією, та використовується, наприклад, при створенні компіляторів, що перетворюють текст на двійковий файл, що може виконуватись.

Для розбиття рядка на токени можна використати наступний алгоритм:

1. Створити порожній буфер для цифр b
2. Для кожного символу s вхідного рядка r:
   якщо s - цифра, покласти її в буфер b;
   якщо s - пробіл, s пропустити. Якщо b містить цифри, то склеїти їх на числовий токен t, додати t у результат; 
   якщо s - оператор, склеїти цифри з b на числовий токен t, додати t у результат,
   s перетворити на токен та також додати у результат

Зауважте, що токенізація має працювати при будь-якій кількості (від нуля) пробілів між числами та операціями. Тобто вирази 1+3, 1 + 3 або 1+ 3 мають всі обробитись коректно

2. Переведення виразу з інфіксного запису у постфіксний

Звичайний для нас запис арифметичного виразу, як 2 + 3 формально називається інфіксним (infix), через те що оператор находиться "всередині", між двома операндами. Цей же вираз можна записати в префіксній нотації як + 2 3. Цей варіант запису ще називається польською нотацією, на честь математика Яна Лукашевича, що її описав. Префіксна та постфіксна (2 3 +, її ще називають "зворотня польська") нотації цікаві тим, що при записі виразу ними можна повністю уникнути використання дужок і вираз можна обрахувати за один прохід, читаючи його зліва направо.

Для переводу виразу з інфіксного у RPN (Reverse Polish Notation) існує алгоритм, створений у 1961 відомим вченим з галузі комп'ютерних наук Едсгером Дейкстрою. Він називається "алгоритмом сортувальної станції" через схожий принцип як на станції, де формуються з вагонів залізнодорожні потяги. Цей алгоритм використовує стек як структуру даних (використайте реалізацію, що ми розглянули на парі, або напишіть самостійно)

Детально про алгоритм, з псевдокодом та прикладом можна почитати на вікіпедії. На ютубі є багато візуалізацій, наприклад, тут чи тут

3. Обчислення значення виразу

Після того як ми отримали вираз з токенів, складених інверсною польською нотацією, залишилось тільки обчислити його значення, для цього реалізуйте простий алгоритм:

1. Створити порожній стек s
2. Для кожного токену t у виразі:
   якщо t - число, додати його у стек s (push)
   якщо t - оператор, дістати (pop) два числа зі стеку s, виконати над ними цю операцію, результат додати у s
3. Останнє число у стеку - результат

В цій роботі, ви не можете користуватися стандартними типами C# List<> та Stack<>. Можете брати ті що ми написали на лекції, дописавши до них методи, яких вам не вистачає. Клас черги Queue реалізуйте за аналогією зі списком.

Контрольні питання

  1. Як ви розумієте поняття "структура даних"? Що таке інтерфейс (АРІ) структури даних?
  2. Що таке RAM model of computation та для чого використовується Big-O нотація?
  3. Якщо ми говоримо, що певний алгоритм має час виконання O(n^2), що це означає?
  4. Що таке стек, які операції він підтримує? Як можна реалізувати стек? Чим ця структура даних відрізняється від черги?
  5. Що означають абревіатури FIFO та LIFO?

Оцінювання

Максимальний бал - 8 (+2 можливих додаткових бали):

  • розбиття рядку на токени - 1 бал;
  • алгоритм сортувальної станції, операції +,-,* та/ - 3 бали;
  • відповіді на теоретичні питання - 2 бали;
  • виконання додаткового практичного завдання при здачі - 2 бали;
  • реалізація дужок та операції піднесення до степеню ^ - +2 бали

Посилання

  1. Skiena: 3.2 Stacks nad Queues, p.71
  2. Cormen: 10.1 Stacks and queues, p.253
  3. Stack on GeeksForGeeks