Польський інверсний запис: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
Рядок 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/>'''ки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи
::*Якщо символ є
:::1) поки на вер'''<nowiki/>'''шині стека префіксна функція…'''<nowiki/>'''
:::::… АБО операція'''<nowiki/>''' на вершині
::::: … АБО операція на вершині
:::: … виштовхуємо верхній елемент
::: 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 ^ / +
|