Польський інверсний запис: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
Kripakailya (обговорення | внесок)
Dormousse (обговорення | внесок)
Рядок 25:
Зворотний польський запис є зручним для застосування в обчислювальних пристроях. Наприклад, для обчислення виразу
: a + b
 
слід виконати наступнітакі дії:
* обчислити a
* обчислити b
Рядок 31 ⟶ 32:
Саме така послідовність і задається '''польським інверсним записом''':
: a b +
Завдяки цьому ПОЛІЗ здобув досить широке розповсюдження в інженерних [[мікрокалькулятор]]ах та [[мікрокомп'ютер]]ах. Зокрема, такі калькулятори виробляли фірми [[Hewlett-Packard]] ([[HP 9100A]]), [[Texas Instruments]]. Практично всі програмовані калькулятори, що вироблялися в [[СРСР]] ([[Б3-34]], [[MK-52]], [[MK-61]] та ін.інші) застосовували зворотну польську нотацію.
 
Комп'ютерні програми зазвичай під час аналізу формул перетворюють їх на послідовність інструкцій у ПОЛІЗ, і саме в такому порядку вони виконуються.
Рядок 37 ⟶ 38:
На основі постфіксної нотації побудовано мову програмування [[Forth]], також вона безпосередньо застосовується у [[PostScript]].
 
Стековою машиною називається алгоритм, який проводить обчислення за зворотної польської записинотації{{Джерело?}}.
 
== Алгоритм для обчислення значення виразу ==
 
Для всіх символів робимовиконуємо наступнетакі дії:
 
* Якщо '''А<sub>і</sub>''' число, то вкласти його у стек;
* Якщо '''А<sub>і</sub>''' оператор, то:
** Витягуємо іззі стекустека два числа;
** Виконуємо дію із числами і результат вкладаємо в стек;
* Якщо '''А<sub>і</sub>''' є функцією то:
** Витягуємо іззі стекустека одне число;
** Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек;
* В кінці роботи в стеку знаходитиметься результат виразу.
Рядок 57 ⟶ 58:
 
Вираз у польському інверсному записі: 12 2 3 4 * 10 5 / + * +<br />
Порядок дій над ним буде наступнийтакий:
 
<table class=MsoNormalTable border=1 cellspacing=0 cellpadding=0
Рядок 340 ⟶ 341:
::* Якщо символ є '''<nowiki/>'(',''' поміщаємо його в стек;
::*'''<nowiki/>'''Якщо символ є '''<nowiki/>')',''' то:
::::До тих пір, по'''<nowiki/>'''ки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи ззі стека у вихідний рядок. При цьому відкриваюча дужка видаляється ззі стека, але у вихіднувихідний рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідний рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваєвідкриваючу дужку, це означає, що у виразі або невірнонеправильно поставлений розділовий знак, або не узгодженнінеузгодженні дужки.
::*Якщо символ є б'''<nowiki/>'''інарноюбінарною операцією, тоді:
:::1) поки на вер'''<nowiki/>'''шині стека префіксна функція…'''<nowiki/>'''
:::::… АБО операція'''<nowiki/>''' на вершині стекустека пріоритетнішемає більший прі'''<nowiki/>'''оритет ніж '''''o1'''''
::::: … АБО операція на вершині стекустека лівоасоціативналіво-асоціативна з пріоритетом як у '''''o1'''''
:::: … виштовхуємо верхній елемент стекустека ву вихідний рядок;
::: 2) поміщаємо операцію '''''o1''''' ву стек;
* Коли вхідний рядок закінчився, виштовхуємо всі символи стекузі стека ву вихідний рядок. ВУ стеку повинні були залишитись тільки символи операцій; якщо це не так, значить ву виразі не узгодженінеузгоджені дужки.
 
=== Приклад ===
 
Маємо рядок «3 +4 * 2 / (1-5) ^ 2». Потрібно перевести їїйого до польського запису
 
Читаємо «3»
Рядок 378 ⟶ 379:
 
Читаємо «/»
Видаляємо «*» зі стекустека і додаємо до виходу, вставляємо «/» в стек
Вихід: 3 4 2 *
Стек: + /
Рядок 403 ⟶ 404:
 
Читаємо «)»
Видаляємо «-» зі стекустека і додаємо до виходу, видаляємо «(» зі стекустека
Вихід: 3 4 2 * 1 5 -
Стек: + /
Рядок 418 ⟶ 419:
 
Кінець виразу
Витягуємо усі елементи зі стекустека і додаємо до виходу
Вихід: 3 4 2 * 1 5 - 2 ^ / +