---
tags: materials
---
# Стекова машина
:::warning
МАШИНА: https://danbst.github.io/factor-playground/
Завдання 1 (easy): [стекові маніпулятори](#Завдання-на-додаткові-стекові-маніпулятори)
Завдання 2 (easy): [математичні операції](#%D0%97%D0%B0%D0%B2%D0%B4%D0%B0%D0%BD%D0%BD%D1%8F-%D0%BD%D0%B0-%D0%BC%D0%B0%D1%82-%D0%B2%D0%B8%D1%80%D0%B0%D0%B7%D0%B8)
Завдання 3 (normal): [алгоритми зі стеком](#Алгоритми-з-стеком-на-Python)
:::
Стеків двух з і які маніпуляції роблять стеками цими з машина стекова складається з. Необов'язковим словник є, але до стек машини доповненням зручним дуже є.
Але по порядку.
Машини стекової прапредком FORTH був.
## Родослівня FORTH
FORTH, як мова, став прикладом, з якого тисячі різних Фортів було зроблено наступними поколіннями. Кожен другий-третій Forth програміст пише свій Forth (я теж написав), тому їх розвелось дуже і дуже багато різних. Окрім власне Forth, на його основі з'явились:
- Factor
- Joy
- Colorforth
- гг, [BrainClub](http://zzo38computer.org/brainclub/core.bcl)
**Всі ці мови мертві**. Але що дивно, стек машина, яка була в основі Forth, вижила у вигляді "віртуальних машин", і багато з них досі використовуються:
- **PostScript** (мова принетрів) є основою формату електронних документів **PDF**
- **JVM (Java Virtual Machine)** є бекендом для мов Java, Clojure, Groovy, Scala, Kotlin, а її варіант також вбудовано в Android
- **CLR (Common Lanugage Runtime)** [є бекендом для .NET мов](https://en.wikipedia.org/wiki/Common_Intermediate_Language) C#, F#, IronPython, PowerShell
- **CPython Bytecode** --- в стандартному інтерпретаторі Пайтона код перетворюється в байткод, який виконується віртуальною стековою машиною
- **WebAssembly**, або **WASM** --- віртуальна машина в браузерах, яка дозволяє виконувати скрипти та код ефективніше ніж JavaScript, також має в основі стекову машину. Є бекендом для всього, включаючи С та С++
- **Ethereum VM** --- бекенд для Solidity, мови контрактів в блокчейні Ethereum
[На офіційному сайті](https://www.ethervm.io/#opcodes) гарно показані всі доступні операції
## Стек як складова компутації
Щоправда, якщо розглядати виключно стек (без стек машини), він має високу цінність з точки зору програмування:
- виклики функцій утворюють стек викликів і стек локальних областей видимості
- він же відображається як **traceback** коли стається креш в програмі
- рекурсивні виклики подовжують стек. Тільки спеціальний тип під назвою "**хвостова рекурсія**" НЕ використовує стек, але це доступно не у всіх мовах
- від рекурсії можна позбутись, реалізувавши стек самостійно. Наприклад, цим способом рекурсивний QuickSort можна перетворити у нерекурсивний
- стек активно використовується при парсингу виразів
- якщо ваш алгоритм оснований на BACKTRACK, то 95% що ви використовуєте стек (явно або рекурсивно)
- ну і останнє, сайт **Stack Overflow** не дарма має у своїй назві слово "стек". Креш через stack overflow часто трапляється через те, що забули написати код виходу з рекурсії.
## Базова система
Базова система складається з двух стеків, словника команд і стрічки слів (програми). Перший стек називається **"стек параметрів"** (parameter stack), другий стек називається **"стек повернень"** (return stack).
Програма складається з "**слів**" (тобто, команд), які йдуть по порядку і розділяються пробілом. Словом є все, включаючи розділові знаки і числа. Числа є особливими словами, які при виконанні програми одразу додаються в стек. Наприклад, програма
```forth=
2 4 6 8
```
запихне в стек числа 2, 4, 6, 8, і число 2 виявиться на дні стеку, а число 8 --- у вершині стеку.
Якщо потім виконати команду `.` (витягнути елемент зверху стеку і вивести на екран), то на екран виведеться число `8`, а не 2. Якщо ж написати ще 3 крапки (через пробіл), то виведуться всі елементи в стеку:
Окрім крапки (`.`), існує ще кілька базових слів.
### `swap ( a b -- b a )`
Команда `swap` міняє місцями два верхніх елементи стеку:
```forth=
4 20 swap
```
:::info
В дужках вказано як себе ведуть елементи на стеку. Дужки не потрібно писати в коді і існують тільки як коментар для людей.
:::
### `dup ( a -- a a )`
Команда `dup` дублює вершину стеку:
```forth=
12 dup
```
### `drop ( a b -- a )`
Команда `drop` видаляє верхній елемент зі стеку:
```forth=
4 2 drop
```
### `>r` та `r>`
Ці дві команди переносять число з вершини стеку у стек повернень (і назад). Це дозволяє робити маніпуляції над елементами в глибині стеку.
Наприклад, нехай в стек записано числа `2 3 1`. Щоб поміняти місцями числа 2 та 3 (які знаходяться в глибині стеку), потрібно буде виконати таку програму:
```forth=
>r swap r>
```
Звісно, у стек повернень можна класти багато елементів. Треба тільки пам'ятати, що
а) це також стек, а отже хто перший зайшов --- виходить останній
б) в стек повернень можна покласти тільки з стеку параметрів, неможливо число одразу покласти на стек повернень
### `: слово ... ;`
В словник можна додавати нові слова через двокрапку. Наприклад, ця програма
```forth=
: digits 0 1 2 3 4 5 6 7 8 9 ;
```
створює нове слово `digits`, яке при виклику засуне в стек 10 чисел від 0 до 9.
:::warning
Важливо! Після початкового `:` має бути пробіл, перед кінцевим `;` має бути також пробіл. Це також слова, а не синтаксичні конструкції.
:::
### Розширений словник
Окрім базових слів, для роботи з стеком використовуються кілька додаткових, які можна реалізувати через основні слова.
#### `over ( a b -- a b a )`
Слово `over` передостанній елемент копіює на вершину стеку.
```forth=
: over >r dup r> swap ;
1 2 over
```
В результаті в стеку будуть числа `1 2 1`
#### `nip ( a b -- b )`
Слово `nip` видаляє передостанній елемент.
```forth=
: nip >r drop r> ;
1 2 nip
```
В результаті в стеку число 1 видалиться.
### Завдання на додаткові стекові маніпулятори
Реалізувати стекові маніпулятори:
- `2drop ( a b c d -- a b )`
- `2dup ( a b -- a b a b )`
- `3over ( a b c -- a b c a )`
- `3nip ( a b c -- b c )`
- `rot ( a b c -- c a b )`
- `-rot ( a b c -- b c a )`
- `tuck ( a b -- b a b )`
- `3dup ( a b c -- a b c a b c )`
- `4reverse ( a b c d -- d c b a )`
- `r@` --- копіює (а не переміщує) число з стеку повернень на стек параметрів
### Математичні операції
Всі матоперації працюють тільки з стеком параметрів. Якщо якась операція вимагає один аргумент (наприклад, квадратний корінь), то вона змінює тільки верхній елемент стеку. Якщо два (наприклад, плюс, помножити, відняти, розділити) --- то операція виконується над двома верхніми елементами.
- `+ ( a b -- a+b )`
- `- ( a b -- a-b )`
- `* ( a b -- a*b )`
- `/ ( a b -- a/b )`
- `mod ( a b -- остача від ділення a на b )`
- `pow ( a b -- a в степені b )`
- `sqrt ( a -- корінь з a )`
- `sin ( a -- sin(a) )`
:::info
В браузерній версії дробові числа підтримуються, але їх неможливо ввести. Щоб записати дробове число доведеться виконувати ділення. Ось як можна зробити число 0.5:
```
1 2 /
```
:::
### Виконання математичних виразів
Розглянемо такий математичний вираз:
```
1 + 2 + 3 + 4
```
В програмі для стекової машини так його записати неможливо, потрібно цей вираз перетворити у вигляд зручний для стеку. Цей вигляд називається "зворотня польська нотація", "reverse polish notation" (RPN). (нормальний вигляд називається "інфіксна нотація", до-речі).
Перша операція яка виконається, це перший плюс. Він додасть числа 1 та 2
```
1 2 +
```
Далі додається число 3
```
1 2 + 3 +
```
І останнім додається число 4
```
1 2 + 3 + 4 +
```
Це і є RPN запис виразу `((1 + 2) + 3) + 4`. Просто як правило ми дужки не пишемо, але для перетворення у RPN важливо знати, в якому порядку ми виконуємо операції. Наприклад
```
1 2 3 4 + + +
```
порахує це саме, але це запис для `1 + (2 + (3 + 4))`.
Якщо ви помітили, то в RPN запису немає дужок. І це основна фішка цього запису --- дужки не потрібні. Ви самі вибираєте, коли і які робити операції. Правило "множення виконується перед додаванням" тут не діє.
Наприклад, ось два вирази
- `10 + 20 * 30`
- `(10 + 20) * 30`
При інфіксній нотації ми повинні ставити дужки, щоб операції виконувались в порядку запису. В RPN же нам дужки не знадобляться:
- `20 30 * 10 +` == `10 + 20 * 30`
- `10 20 + 30 *` == `(10 + 20) * 30`
Ми навіть можемо записати ці вирази по різному:
- `10 20 30 * +` == `10 + 20 * 30`
- `30 10 20 + *` == `(10 + 20) * 30`
### Завдання на мат вирази
Реалізувати слова:
- `+100500 ( a -- a+100500 )`
- `neg ( a -- -a )`. Використати той факт, що якщо від 0 відняти число, то ми отримаємо його від'ємне значення
- `sqr ( a -- a^2 )` --- квадрат числа
- `0.5 ( -- 0.5 )` --- просто число 0.5
- `pi ( -- pi )` --- просто число $\pi$. Реалізувати через ділення двох чисел
- `circle.area ( r -- S )` --- формула площі круга $S = \pi r^2$
- `cos ( x -- cos(x) )` --- реалізувати косинус через `sin` через формулу $$\cos{x} = \sin{(x+\pi/2)}$$
- `tan (x -- tan(x) )` --- реалізувати тангенс через $sin(x)/cos(x)$
- `solve.quadratic ( a b c -- x1 x2 )` --- отримати два розв'язки квадратного рівняння $$ax^2+bx+c = 0$$
Вважати, що розв'язки існують.
# Алгоритми з стеком на Python
Стек легко реалізувати на основі списку. Зі стеком є три операції: push, pop та isEmpty:
```python=
stack = [] # list is perfect as stack
stack.append(10) # push to stack
if stack: # check if stack is not empty
x = stack.pop(-1) # pop last element from stack
```
## Реалізувати стек машину
Реалізувати стек машину з усіма описаними вище операціями, включаючи додавання нових слів через `:`.
## Перевірка правильності вкладених дужок
Нехай є рядок з дужок. Наприклад,
```
[(([()])[])] # правильно
[(])((())) # неправильно
]()()()[ # також неправильно
```
Потрібно написати програму, яка буде перевіряти на коректність вкладеності дужок.
## Вкладеність дужок в лапках
Те саме, тільки потрібно перевіряти коректність вкладеності лапок, а дужки в лапках треба ігнорувати.
```
(("}{}"){'a'})[0]
```
## Індекс дужки, яка закриває (або відкриває) дану
Нехай дано рядок з дужками:
```
tree = ("a", "b", {"b", ("c")})
```
і дано індекс в цьому рядку, який вказує на якусь дужку або лапку. Потрібно знайти індекс дужки яка відкриває або закриває дану.
:::info
Цей алгоритм використовується в редакторі коду для підсвітки відповідних дужок та лапок!
:::
## Просте виконання виразу
В пайтоні є магічна команда `eval()`, яка дозволяє запустити рядок як код:
Але як ця магія працює? Ваше завдання написати свій eval для спрощеного варіанту виразів:
- є тільки додавання та множення
- немає дужок
- множення має пріоритет перед додаванням
## Складне виконання виразу
Виконати попереднє завдання, але додатково врахувати що у виразі можуть бути дужки.
## Floodfill
Реалізувати алгоритм заливки.
Нехай є матриця з чисел:
```python=
matrix = [
[0,0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,0,0],
[0,1,0,0,0,0,0,1,0],
[0,1,0,0,0,0,0,1,0],
[0,1,0,0,0,0,0,1,0],
[0,1,0,0,0,0,0,1,0],
[0,0,1,1,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0],
]
```
Потрібно заповнити область цієї матриці двійками до межи з одиничок, починаючи з певної точки. Наприклад, якщо почати з центру матриці, то в результаті вийде:
```python=
filled_matrix = [
[0,0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,0,0],
[0,1,2,2,2,2,2,1,0],
[0,1,2,2,2,2,2,1,0],
[0,1,2,2,2,2,2,1,0],
[0,1,2,2,2,2,2,1,0],
[0,0,1,1,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0],
]
```
Алгоритм:
1. Додаємо у стек початкову точку
2. Поки в стеку є точки:
- дістаємо (pop) точку з стеку
- ставимо у цю точку число 2
- перевірямо точки зверху, знизу, справа та зліва чи якісь з них дорівнюють 2 або 1
- ті які != 2 та != 1 додаємо у стек (пари координат) і ставимо туди 2
Sign in with Wallet
Connect another wallet