Обратен полски запис
Обратният полски запис (Reverse Polish notation (RPN)) е математически запис (нотация), в която всеки оператор следва всички негови операнди, за разлика от полския запис, който поставя оператора преди неговите операнди. Обратният полски запис също като постфиксния запис не се нуждае от никакви скоби, при условие че всеки оператор има фиксиран брой операнди. Описанието „полска“ се отнася до националността на полския логик Ян Лукашевич, който е изобретил полския запис през 1920 година.[1][2]
Обратният полски запис е предложен през 1954 г. от Бъркс, Уорън, и Райт и е независимо преоткрит от Ф. Л. Бауър и Е. У. Дейкстра в началото на 60-те години на 20 век, за да се намали достъпът до компютърна памет и да се използва стека, за да се изчисли израза. Алгоритмите и нотацията за тази схема са разширени от австралийския философ и компютърен учен Чарлз Хъмблин в средата на 50-те години на 20 век.[3]
През 1970-те и 1980-те години, обратният полски запис е добре известен на много потребители на изчислителни машини, като Хюлет-Пакард го използват в своя пионерски 9100A и в научните калкулатори HP-35, в следващата Voyager серия – а също и „култовия“ финансов калкулатор HP-12C.
В компютърните науки, постфиксният запит често се използва в стек-базираните и програмни езици. Също така е често срещан и в потока на снабдително-базирани системи, включително UNIX-базирани операционни системи.
Повечето от това, което следва, е свързано с бинарни оператори. Пример за едноаргументен оператор, чиято стандартна нотация използва постфиксната е факториелът.
Дефиниция
[редактиране | редактиране на кода]В обратния полски запис операторите следват своите операнди. Например, за да съберем 3 и 4, ще напишем „3 4 +“, отколкото „3 + 4“. Ако има множествени операции, операторът е даден веднага след втория операнд, така че ако изразът е написан „3 – 4 + 5“ в конвенционална нотация ще бъде написан по следния начин „3 4 – 5 +“. В обратния полски запис първо 4 е изведено от 3, след което е прибавено 5 към тях. Предимството на обратния полски запис е това, че премахва нуждата от скоби, които се изискват в инфиксната нотация. Докато " 3 – 4 * 5 " също може да бъде написано " 3 – (4 * 5) ", което означава нещо много по-различно от " (3 – 4) * 5. Предходният израз също може да бъде написан " 3 4 5 * – ", което недвусмислено означава " 3 (4 5 *) – ", което намалява до "3 20 – " последното може да бъде написано и като "3 4 – 5 * " (или 5 3 4 – *, ако се поддържа сходен формат), което недвусмислено означава " (3 4 – ) 5 * ".
Въпреки името, обратният полски запис не е точно обратното на полския запис, за операнди на некомутативни операции са все още написани в конвенционалния ред (например " ÷ 6 3 " в полски запис и " 6 3 ÷ " в обратен полски, и двете са равни на 2, докато " 3 6 ÷ " в обратен полски запис ще бъде равно на 1/2).
Практически приложения
[редактиране | редактиране на кода]При сравнителни тестове на обратния полски запис с алгебричен запис се установява, че обратният полски запис води до по-бързи изчисления поради две причини. Изчисленията на обратния полски запис нямат нужда от изрази, за да бъдат параметризирани, по-малко операции трябва да бъдат вкарани, за да се извършат обичайните изчисления. Като допълнение, при изчисленията с обратен полски запис се правят по-малко грешки, отколкото при другите типове на изчисления. По-късно проучване показва, че увеличената скорост от обратния полски запис може да е сведена до по-малкия брой на натискане на клавишите необходим да се въведе тази нотация, отколкото по-малкия познавателен товар на неговите потребители. Въпреки това, много доказателства показват, че обратният полски запис е по-труден за научаване от потребителите, отколкото алгебричната анотация.
Първите компютри с архитектура, позволяваща използването на обратен полски запис, са създадени през 1960 година. Комерсиалната им употреба се свързва с различните модели научни и бизнес калкулатори, разработени от Хюлет-Пакард.
Съвременната употреба на обратния полски запис се свързва с различни модели хардуерни калкулатори, както и някои софтуерни приложения като MAC OS X Calculator, Android RealCalc Scientific Calculator и други.
Алгоритъм за преобразуване
[редактиране | редактиране на кода]Има няколко начина за преобразуване на стандартен израз в обратен полски запис, най-известният от които е алгоритъмът „Shunting-yard“, изведен от холандския компютърен пионер Едсхер Дейкстра през 1961 г. Името на алгоритъма буквално може да се преведе като „обръщач, място за обръщане“, тъй като операциите му напомняли на Дейкстра за мястото, където влаковете извършвали своите обратни маневри.
Алгоритъм за изчисляване на резултат
[редактиране | редактиране на кода]Алгоритъмът за изчисляване на резултат на израз, записан с обратен полски запис, е сравнително лесен. За целта се използва структурата от данни Стек (Stack).
- За всеки пореден символ се извършва една от следните операции:
- Ако символът е число:
- добавяме числото в стека
- Ако символът е оператор (операторът може да включва и функции):
- Знае се, че операторът използва n аргумента – за стандартните математически операции събиране, изваждане, умножение, деление и степенуване се използват два аргумента – n = 2
- Ако в стека има по-малко от n числа:
- Грешка – потребителят е въвел непълен израз – пример: "3 + "
- Ако има достатъчно числа, изваждаме n на брой от стека
- Извършваме операцията
- Добавяме в стека резултата от операцията
- Ако символът е число:
- След като изпълним горните операции за всеки символ в записа:
- Ако има останало само едно число в стека:
- числото е резултатът от израза
- Ако има повече от едно число
- Грешка – потребителят е въвел непълен израз
- Ако има останало само едно число в стека:
Пример
[редактиране | редактиране на кода]Стандартният запис на израза „5 + ((1 + 2) * 4) – 3“ може да бъде записан по следния начин с обратен полски запис, като за трансформацията използваме алгоритъма „Shunting-yard“:
5 1 2 + 4 * + 3 –
Изразът се оценява от ляво надясно, както е посочено в долната таблица:
| Символ | Операция | Стек | Коментари |
|---|---|---|---|
| 5 | stack.Push(5) | 5 | Символът е число, добавяме го към стека |
| 1 | stack.Push(1) | 5, 1 | Символът е число, добавяме го към стека |
| 2 | stack.Push(2) | 5, 1, 2 | Символът е число, добавяме го към стека |
| + | stack.Pop() = 2
stack.Pop() = 1 stack.Push(1 + 2) |
5, 3 | Символът е оператор. Изваждаме нужния брой аргументи от
стека, извършваме операцията, и добавяме резултата в стека |
| 4 | stack.Push(4) | 5, 3, 4 | Символът е число, добавяме го към стека |
| * | stack.Pop() = 4
stack.Pop() = 3 stack.Push(3 * 4) |
5, 12 | Символът е оператор. Изваждаме нужния брой аргументи от
стека, извършваме операцията, и добавяме резултата в стека |
| + | stack.Pop() = 12
stack.Pop() = 5 stack.Push(5 + 12) |
17 | Символът е оператор. Изваждаме нужния брой аргументи от
стека, извършваме операцията, и добавяме резултата в стека |
| 3 | stack.Push(3) | 17, 3 | Символът е число, добавяме го към стека |
| - | stack.Pop() = 3
stack.Pop() = 17 stack.Push(17 – 3) |
14 | Символът е оператор. Изваждаме нужния брой аргументи от
стека, извършваме операцията, и добавяме резултата в стека |
| Резултат: | 14 | Символите са изчерпани, единственото останало число в стека
е търсеният резултат |
След извършване на изчисленията за всеки символ в израза, последното останало число в стека, в случая 14, е търсеният резултат.
Източници
[редактиране | редактиране на кода]- ↑ Хамблин [1962]: преводи към и от полски запис. Компютърен вестник, 5: 210 – 213.
- ↑ Ball, John A. (1978). Алгоритми за RPN калкулатори. Кеймбридж, Масачузетс, САЩ: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8.
- ↑ „Чарлз Л. Хамблин и неговата работа“ от Питър Макбърни
 
|
Тази страница частично или изцяло представлява превод на страницата Reverse Polish notation в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.
ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни. |