Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Зворо тний по льський за пис зворотний бездужковий запис постфіксна нотація польський інверсний запис ПОЛІЗ англ RPN Rev

Польський інверсний запис

Зворо́тний по́льський за́пис (зворотний бездужковий запис, постфіксна нотація, польський інверсний запис (ПОЛІЗ), англ. RPN — Reverse Polish Notation) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.

Історія розробки

Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин [en] у середині 1950-х років на основі польської нотації, яку запропонував 1920 року польський математик Ян Лукашевич. Роботу Гембліна представлено на конференції в червні 1957 року, і видано в 1957 і 1962 роках.

Першими комп'ютерами, що підтримують зворотний польський запис були [en] від English Electric Company, який був випущений в 1963, і американський (Burroughs B5000), випущений в тому ж 1963. Зворотна польська нотація застосовувалася в радянському інженерному калькуляторі Б3-19М, випущеному в 1976 році. Майже всі програмовані калькулятори в СРСР аж до кінця 1980-х років використовували ПОЛІЗ — він простіше реалізовувався і дозволяв обійтися в програмуванні обчислень меншим числом команд, порівняно зі звичайною алгебраїчною нотацією, адже обсяг програмної пам'яті в цих моделях завжди було критичним ресурсом.

Загальний вигляд

У загальному вигляді запис виглядає так:

  • Запис набору операцій складається з послідовності операндів і знаків операцій. Операнди у виразі при письмовому записі розділяються пробілами.
  • Вираз читається зліва направо. Коли у виразі зустрічається знак операції, виконується відповідна операція над двома останніми перед ним операндами в порядку їх запису. Результат операції замінює у вираженні послідовність її операндів і її знак, після чого вираз обчислюється далі за тим же правилом.
  • Результатом обчислення виразу стає результат останньої обчисленої операції.

Приклади

Вираз Традиційна (інфіксна) нотація Зворотна польська (постфіксна) нотація
a + b × c a + b*c a b c * +
(a + b) × (c + d) (a + b) * (c + d) a b + c d + *
(a + t) × (b × (a + c))(c + d) (a + t) * (b * (a + c))^(c + d) a t + b a c + * c d + ^ *

Застосування

Зворотний польський запис є зручним для застосування в обчислювальних пристроях. Наприклад, для обчислення виразу: a + b

слід виконати такі дії:

  • обчислити a
  • обчислити b
  • скласти результати

Саме така послідовність і задається польським інверсним записом:

a b +

Комп'ютерні програми зазвичай під час аналізу формул перетворюють їх на послідовність інструкцій у ПОЛІЗ, і саме в такому порядку вони виконуються.

На основі постфіксної нотації побудовано мову програмування Forth, також вона безпосередньо застосовується у PostScript.

[en] називається алгоритм, який проводить обчислення за зворотною польською нотацією[]. Прикладом використання стекової машини є програма UNIX dc.

Калькулятори

ПОЛІЗ здобув досить широке розповсюдження в інженерних (мікрокалькуляторах) та мікрокомп'ютерах. Зокрема, такі калькулятори виробляли фірми Hewlett-Packard (), Texas Instruments (програмно). Практично всі програмовані калькулятори, що вироблялися в СРСР (Б3-34, , та інші) застосовували зворотну польську нотацію.

Створено кілька калькуляторів з підтримкою ПОЛІЗ та відкритим апаратним забезпеченням, наприклад OpenRPNCalc, кишеньковий інженерний калькулятор на базі мікропроцесора STMicroelectronics STM32 (модель STM32L476).

Алгоритм для обчислення значення виразу

Для всіх символів виконуємо такі дії:

  • Якщо Аі число, то вкласти його у стек;
  • Якщо Аі оператор, то:
    • Витягуємо зі стека два числа;
    • Виконуємо дію із числами і результат вкладаємо в стек;
  • Якщо Аі є функцією то:
    • Витягуємо зі стека одне число;
    • Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек;
  • В кінці роботи в стеку знаходитиметься результат виразу.

Приклад

Маємо вираз: 12 + 2 * ((3 * 4) + (10 / 5))

Вираз у польському інверсному записі: 12 2 3 4 * 10 5 / + * +
Порядок дій над ним буде такий:

Крок Елемент Стек
1 12 12
2 2 2 12
3 3 3 2 12
4 4 4 3 2 12
5 * 12 2 12
6 10 10 12 2 12
7 5 5 10 12 2 12
8 / 2 12 2 12
9 + 14 2 12
10 * 28 12
11 + 40

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

  • Поки ще є символи для зчитування:
  • Читаємо наступний символ;
  • Якщо символ є числом або постфіксною функцією (наприклад, ! — факторіал), то додаємо до вихідного рядка;
  • Якщо символ є префіксною функцією (наприклад, sin — синус), поміщаємо його в стек;
  • Якщо символ є '(', поміщаємо його в стек;
  • Якщо символ є ')', то:
До тих пір, поки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи зі стека у вихідний рядок. При цьому відкриваюча дужка видаляється зі стека, але у вихідний рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідний рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваючу дужку, це означає, що у виразі або неправильно поставлений розділовий знак, або неузгодженні дужки.
  • Якщо символ є бінарною операцією, тоді:
1) поки на вершині стека префіксна функція…
… АБО операція на вершині стека має більший пріоритет ніж o1
… АБО операція на вершині стека ліво-асоціативна з пріоритетом як у o1
… виштовхуємо верхній елемент стека у вихідний рядок;
2) поміщаємо операцію o1 у стек;
  • Коли вхідний рядок закінчився, виштовхуємо всі символи зі стека у вихідний рядок. У стеку повинні були залишитись тільки символи операцій; якщо це не так, значить у виразі неузгоджені дужки.

Приклад

Маємо рядок «3 + 4 * 2 / (1-5) ^ 2». Потрібно перевести його до польського запису 

Читаємо «3» Додаємо «3» до виходу Вихід: 3 
Читаємо «+» Вставляємо «+» в стек Вихід: 3 Стек: + 
Читаємо «4» Додаємо «4» до виходу Вихід: 3 4 Стек: + 
Читаємо «*» Вставляємо «*» в стек Вихід: 3 4 Стек: + * 
Читаємо «2» Додаємо «2» до виходу Вихід: 3 4 2 Стек: + * 
Читаємо «/» Видаляємо «*» зі стека і додаємо до виходу, вставляємо «/» в стек Вихід: 3 4 2 * Стек: + / 
Читаємо «(» Вставляємо «(» в стек Вихід: 3 4 2 * Стек: + / ( 
Читаємо «1» Додаємо «1», до виходу Вихід: 3 4 2 * 1 Стек: + / ( 
Читаємо «-» Вставляємо «-» в стек Вихід: 3 4 2 * 1 Стек: + / (- 
Читаємо «5» Додаємо «5» до виходу Вихід: 3 4 2 * 1 5 Стек: + / (- 
Читаємо «)» Видаляємо «-» зі стека і додаємо до виходу, видаляємо «(» зі стека Вихід: 3 4 2 * 1 5 - Стек: + / 
Читаємо «^» Додаємо «^» в стек Вихід: 3 4 2 * 1 5 - Стек: + / ^ 
Читаємо «2» Додаємо «2» до виходу Вихід: 3 4 2 * 1 5 - 2 Стек: + / ^ 
Кінець виразу Витягуємо усі елементи зі стека і додаємо до виходу Вихід: 3 4 2 * 1 5 - 2 ^ / +


Див. також

Посилання

Ця стаття не містить . Ви можете допомогти поліпшити цю статтю, додавши посилання на . Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2015)
  1. Складанюк, Максим (2020). Арифметичний калькулятор (Курсова робота) (укр.). Бердичів, Україна.
  2. RPN. www.hpmuseum.org. Процитовано 3 жовтня 2023.
  3. Solution 11904: Using Reverse Polish Notation (RPN) on TI Calculators. education.ti.com (англ.). Процитовано 3 жовтня 2023.
  4. Poluektov, Anton (17 вересня 2023), OpenRPNCalc, процитовано 3 жовтня 2023
  5. List, Jenny (5 червня 2021). An Open-source Scientific RPN Calculator. Hackaday (амер.). Процитовано 3 жовтня 2023.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Дата публікації:
Zvoro tnij po lskij za pis zvorotnij bezduzhkovij zapis postfiksna notaciya polskij inversnij zapis POLIZ angl RPN Reverse Polish Notation forma zapisu matematichnih viraziv v yakij znaki operacij roztashovano pislya operandiv Roztashuvannya znakiv operacij pered operandami vikoristovuye polska notaciya Istoriya rozrobkiZvorotnij polskij zapis rozrobiv avstralijskij filosof i fahivec u galuzi teoriyi obchislyuvalnih mashin en u seredini 1950 h rokiv na osnovi polskoyi notaciyi yaku zaproponuvav 1920 roku polskij matematik Yan Lukashevich Robotu Gemblina predstavleno na konferenciyi v chervni 1957 roku i vidano v 1957 i 1962 rokah Pershimi komp yuterami sho pidtrimuyut zvorotnij polskij zapis buli en vid English Electric Company yakij buv vipushenij v 1963 i amerikanskij Burroughs B5000 vipushenij v tomu zh 1963 Zvorotna polska notaciya zastosovuvalasya v radyanskomu inzhenernomu kalkulyatori B3 19M vipushenomu v 1976 roci Majzhe vsi programovani kalkulyatori v SRSR azh do kincya 1980 h rokiv vikoristovuvali POLIZ vin prostishe realizovuvavsya i dozvolyav obijtisya v programuvanni obchislen menshim chislom komand porivnyano zi zvichajnoyu algebrayichnoyu notaciyeyu adzhe obsyag programnoyi pam yati v cih modelyah zavzhdi bulo kritichnim resursom Zagalnij viglyadU zagalnomu viglyadi zapis viglyadaye tak Zapis naboru operacij skladayetsya z poslidovnosti operandiv i znakiv operacij Operandi u virazi pri pismovomu zapisi rozdilyayutsya probilami Viraz chitayetsya zliva napravo Koli u virazi zustrichayetsya znak operaciyi vikonuyetsya vidpovidna operaciya nad dvoma ostannimi pered nim operandami v poryadku yih zapisu Rezultat operaciyi zaminyuye u virazhenni poslidovnist yiyi operandiv i yiyi znak pislya chogo viraz obchislyuyetsya dali za tim zhe pravilom Rezultatom obchislennya virazu staye rezultat ostannoyi obchislenoyi operaciyi PrikladiViraz Tradicijna infiksna notaciya Zvorotna polska postfiksna notaciya a b c a b c a b c a b c d a b c d a b c d a t b a c c d a t b a c c d a t b a c c d ZastosuvannyaZvorotnij polskij zapis ye zruchnim dlya zastosuvannya v obchislyuvalnih pristroyah Napriklad dlya obchislennya virazu a b slid vikonati taki diyi obchisliti a obchisliti b sklasti rezultati Same taka poslidovnist i zadayetsya polskim inversnim zapisom a b Komp yuterni programi zazvichaj pid chas analizu formul peretvoryuyut yih na poslidovnist instrukcij u POLIZ i same v takomu poryadku voni vikonuyutsya Na osnovi postfiksnoyi notaciyi pobudovano movu programuvannya Forth takozh vona bezposeredno zastosovuyetsya u PostScript en nazivayetsya algoritm yakij provodit obchislennya za zvorotnoyu polskoyu notaciyeyu dzherelo Prikladom vikoristannya stekovoyi mashini ye programa UNIX dc Kalkulyatori POLIZ zdobuv dosit shiroke rozpovsyudzhennya v inzhenernih mikrokalkulyatorah ta mikrokomp yuterah Zokrema taki kalkulyatori viroblyali firmi Hewlett Packard Texas Instruments programno Praktichno vsi programovani kalkulyatori sho viroblyalisya v SRSR B3 34 ta inshi zastosovuvali zvorotnu polsku notaciyu Stvoreno kilka kalkulyatoriv z pidtrimkoyu POLIZ ta vidkritim aparatnim zabezpechennyam napriklad OpenRPNCalc kishenkovij inzhenernij kalkulyator na bazi mikroprocesora STMicroelectronics STM32 model STM32L476 Algoritm dlya obchislennya znachennya virazuDlya vsih simvoliv vikonuyemo taki diyi Yaksho Ai chislo to vklasti jogo u stek Yaksho Ai operator to Vityaguyemo zi steka dva chisla Vikonuyemo diyu iz chislami i rezultat vkladayemo v stek Yaksho Ai ye funkciyeyu to Vityaguyemo zi steka odne chislo Viznachayemo znachennya funkciyi iz vidpovidnim argumentom ta pomishayemo rezultat u stek V kinci roboti v steku znahoditimetsya rezultat virazu Priklad Mayemo viraz 12 2 3 4 10 5 Viraz u polskomu inversnomu zapisi 12 2 3 4 10 5 Poryadok dij nad nim bude takij Krok Element Stek 1 12 12 2 2 2 12 3 3 3 2 12 4 4 4 3 2 12 5 12 2 12 6 10 10 12 2 12 7 5 5 10 12 2 12 8 2 12 2 12 9 14 2 12 10 28 12 11 40Algoritm dlya peretvorennya zvichajnogo zapisu v bezduzhkovijPoki she ye simvoli dlya zchituvannya Chitayemo nastupnij simvol Yaksho simvol ye chislom abo postfiksnoyu funkciyeyu napriklad faktorial to dodayemo do vihidnogo ryadka Yaksho simvol ye prefiksnoyu funkciyeyu napriklad sin sinus pomishayemo jogo v stek Yaksho simvol ye pomishayemo jogo v stek Yaksho simvol ye to Do tih pir poki verhnim elementom steka ne stane vidkrivayucha duzhka vishtovhuyemo elementi zi steka u vihidnij ryadok Pri comu vidkrivayucha duzhka vidalyayetsya zi steka ale u vihidnij ryadok ne dodayetsya Yaksho pislya cogo kroku na vershini steka viyavlyayetsya simvol funkciyi vishtovhuyemo jogo u vihidnij ryadok Yaksho stek zakinchivsya ranishe nizh mi zustrili vidkrivayuchu duzhku ce oznachaye sho u virazi abo nepravilno postavlenij rozdilovij znak abo neuzgodzhenni duzhki dd Yaksho simvol ye binarnoyu operaciyeyu todi 1 poki na vershini steka prefiksna funkciya ABO operaciya na vershini steka maye bilshij prioritet nizh o1 ABO operaciya na vershini steka livo asociativna z prioritetom yak u o1 dd vishtovhuyemo verhnij element steka u vihidnij ryadok dd 2 pomishayemo operaciyu o1 u stek dd dd Koli vhidnij ryadok zakinchivsya vishtovhuyemo vsi simvoli zi steka u vihidnij ryadok U steku povinni buli zalishitis tilki simvoli operacij yaksho ce ne tak znachit u virazi neuzgodzheni duzhki Priklad Mayemo ryadok 3 4 2 1 5 2 Potribno perevesti jogo do polskogo zapisu Chitayemo 3 Dodayemo 3 do vihodu Vihid 3 Chitayemo Vstavlyayemo v stek Vihid 3 Stek Chitayemo 4 Dodayemo 4 do vihodu Vihid 3 4 Stek Chitayemo Vstavlyayemo v stek Vihid 3 4 Stek Chitayemo 2 Dodayemo 2 do vihodu Vihid 3 4 2 Stek Chitayemo Vidalyayemo zi steka i dodayemo do vihodu vstavlyayemo v stek Vihid 3 4 2 Stek Chitayemo Vstavlyayemo v stek Vihid 3 4 2 Stek Chitayemo 1 Dodayemo 1 do vihodu Vihid 3 4 2 1 Stek Chitayemo Vstavlyayemo v stek Vihid 3 4 2 1 Stek Chitayemo 5 Dodayemo 5 do vihodu Vihid 3 4 2 1 5 Stek Chitayemo Vidalyayemo zi steka i dodayemo do vihodu vidalyayemo zi steka Vihid 3 4 2 1 5 Stek Chitayemo Dodayemo v stek Vihid 3 4 2 1 5 Stek Chitayemo 2 Dodayemo 2 do vihodu Vihid 3 4 2 1 5 2 Stek Kinec virazu Vityaguyemo usi elementi zi steka i dodayemo do vihodu Vihid 3 4 2 1 5 2 Div takozhStekova mova programuvannyaPosilannyaCya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno listopad 2015 Skladanyuk Maksim 2020 Arifmetichnij kalkulyator Kursova robota ukr Berdichiv Ukrayina RPN www hpmuseum org Procitovano 3 zhovtnya 2023 Solution 11904 Using Reverse Polish Notation RPN on TI Calculators education ti com angl Procitovano 3 zhovtnya 2023 Poluektov Anton 17 veresnya 2023 OpenRPNCalc procitovano 3 zhovtnya 2023 List Jenny 5 chervnya 2021 An Open source Scientific RPN Calculator Hackaday amer Procitovano 3 zhovtnya 2023
Топ