---
# System prepended metadata

title: Стекова машина
tags: [materials]

---

---
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 був.

![](https://i.imgur.com/EhD4HP8.png)

## Родослівня FORTH

FORTH, як мова, став прикладом, з якого тисячі різних Фортів було зроблено наступними поколіннями. Кожен другий-третій Forth програміст пише свій Forth (я теж написав), тому їх розвелось дуже і дуже багато різних. Окрім власне Forth, на його основі з'явились:

- Factor
- Joy
- Colorforth
- гг, [BrainClub](http://zzo38computer.org/brainclub/core.bcl)

**Всі ці мови мертві**. Але що дивно, стек машина, яка була в основі Forth, вижила у вигляді "віртуальних машин", і багато з них досі використовуються:

- **PostScript** (мова принетрів) є основою формату електронних документів **PDF**
  ![](https://i.imgur.com/BFISCWb.png)
- **JVM (Java Virtual Machine)** є бекендом для мов Java, Clojure, Groovy, Scala, Kotlin, а її варіант також вбудовано в Android
  ![](https://i.imgur.com/yjmdf3S.png)
- **CLR (Common Lanugage Runtime)** [є бекендом для .NET мов](https://en.wikipedia.org/wiki/Common_Intermediate_Language) C#, F#, IronPython, PowerShell
  ![](https://i.imgur.com/lnn9uI7.png =300x)
- **CPython Bytecode** --- в стандартному інтерпретаторі Пайтона код перетворюється в байткод, який виконується віртуальною стековою машиною
  ![](https://i.imgur.com/sFizKpd.png =500x)
  ![](https://i.imgur.com/KpBChrn.png)

- **WebAssembly**, або **WASM** --- віртуальна машина в браузерах, яка дозволяє виконувати скрипти та код ефективніше ніж JavaScript, також має в основі стекову машину. Є бекендом для всього, включаючи С та С++
  ![](https://i.imgur.com/ld3CLWQ.png =500x)
- **Ethereum VM** --- бекенд для Solidity, мови контрактів в блокчейні Ethereum
  ![](https://i.imgur.com/X6La1Uu.png)
  [На офіційному сайті](https://www.ethervm.io/#opcodes) гарно показані всі доступні операції


## Стек як складова компутації

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

- виклики функцій утворюють стек викликів і стек локальних областей видимості
    - він же відображається як **traceback** коли стається креш в програмі
      ![](https://i.imgur.com/hLBI4Wm.png)
- рекурсивні виклики подовжують стек. Тільки спеціальний тип під назвою "**хвостова рекурсія**" НЕ використовує стек, але це доступно не у всіх мовах
  ![](https://i.imgur.com/b3XBXb4.png)
- від рекурсії можна позбутись, реалізувавши стек самостійно. Наприклад, цим способом рекурсивний QuickSort можна перетворити у нерекурсивний
  ![](https://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif)
- стек активно використовується при парсингу виразів
  ![](https://i.imgur.com/3mFOb8U.png)
- якщо ваш алгоритм оснований на BACKTRACK, то 95% що ви використовуєте стек (явно або рекурсивно)
  ![](https://rosettacode.org/mw/images/9/90/Mazesolve_bbc.gif)
- ну і останнє, сайт **Stack Overflow** не дарма має у своїй назві слово "стек". Креш через stack overflow часто трапляється через те, що забули написати код виходу з рекурсії.
  ![](https://i.imgur.com/WdXwGST.png)

## Базова система

Базова система складається з двух стеків, словника команд і стрічки слів (програми). Перший стек називається **"стек параметрів"** (parameter stack), другий стек називається **"стек повернень"** (return stack).

Програма складається з "**слів**" (тобто, команд), які йдуть по порядку і розділяються пробілом. Словом є все, включаючи розділові знаки і числа. Числа є особливими словами, які при виконанні програми одразу додаються в стек. Наприклад, програма

```forth=
2 4 6 8
```
запихне в стек числа 2, 4, 6, 8, і число 2 виявиться на дні стеку, а число 8 --- у вершині стеку. 

![](https://i.imgur.com/6Akob3p.png)

Якщо потім виконати команду `.` (витягнути елемент зверху стеку і вивести на екран), то на екран виведеться число `8`, а не 2. Якщо ж написати ще 3 крапки (через пробіл), то виведуться всі елементи в стеку:
![](https://i.imgur.com/6MxDpk4.png)
![](https://i.imgur.com/wE8cIln.png)

Окрім крапки (`.`), існує ще кілька базових слів.

### `swap ( a b -- b a )`

Команда `swap` міняє місцями два верхніх елементи стеку:
```forth=
4 20 swap
```
![](https://i.imgur.com/rVNJtCH.png)

:::info
В дужках вказано як себе ведуть елементи на стеку. Дужки не потрібно писати в коді і існують тільки як коментар для людей.
:::

### `dup ( a -- a a )`

Команда `dup` дублює вершину стеку:
```forth=
12 dup
```

![](https://i.imgur.com/kk48azE.png)

### `drop ( a b -- a )`

Команда `drop` видаляє верхній елемент зі стеку:
```forth=
4 2 drop
```

![](https://i.imgur.com/MUD8sYS.png)

### `>r` та `r>`

Ці дві команди переносять число з вершини стеку у стек повернень (і назад). Це дозволяє робити маніпуляції над елементами в глибині стеку.

Наприклад, нехай в стек записано числа `2 3 1`. Щоб поміняти місцями числа 2 та 3 (які знаходяться в глибині стеку), потрібно буде виконати таку програму:

```forth=
>r swap r>
```

![](https://i.imgur.com/HUNku22.png)

Звісно, у стек повернень можна класти багато елементів. Треба тільки пам'ятати, що
а) це також стек, а отже хто перший зайшов --- виходить останній
б) в стек повернень можна покласти тільки з стеку параметрів, неможливо число одразу покласти на стек повернень

### `: слово ... ;`

В словник можна додавати нові слова через двокрапку. Наприклад, ця програма
```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()`, яка дозволяє запустити рядок як код:

![](https://i.imgur.com/nQxtHLY.png)

Але як ця магія працює? Ваше завдання написати свій 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

