Обратная польская запись

    Два плюс два, умножить на два?

    Не знаю как вы, но я в школе долго мучился, пытаясь разобраться с приоритетом операций и скобками. Потом, как и каждый начинающий программист, я мучился с приоритетом операций и скобками, когда писал собственный калькулятор. А оказалось, что все эти мучения были напрасны. Ведь существует прекрасный механизм, известный, как обратная польская запись. О том, что это такое и как с этим работать я и хочу вам рассказать.

    В математике существует древняя традиция помещать оператор между операндами (x+y), а не после операндов (xy+). Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича (1958), который изучал свойства этой записи.
    Обратная польская запись имеет ряд преимуществ перед инфиксной записью при выражении алгебраических формул. Во-первых, любая формула может быть выражена без скобок. Во-вторых, она удобна для вычисления формул в машинах со стеками. В-третьих, инфиксные операторы имеют приоритеты, которые произвольны и нежелательны. Например, мы знаем, что ab+c значит (ab)+c, а не a(b+c), поскольку произвольно было определено, что умножение имеет приоритет над сложением. Но имеет ли приоритет сдвиг влево перед операцией И? Кто знает? Обратная польская запись позволяет устранить такие недоразумения.

    Постановка задачи
    На вход программы поступает выражение, состоящее из односимвольных идентификаторов и знаков арифметических действий. Требуется преобразовать это выражение в обратную польскую запись или же сообщить об ошибке.

    Алгоритм перевода в обратную польскую запись
    Существует несколько алгоритмов для превращения инфиксных формул в обратную польскую запись. Мы рассмотрим переработанный алгоритм, идее которого предложена Э. Дейкстра (E.W. Dijkstra). Предположим, что формула состоит из переменных, двухоперандных операторов +,-,*,/,^, а также левой и правой скобок. Чтобы отметить конец формулы, мы будем вставлять символ после её последнего символа и перед первым символом следующей формулы.


    На рисунке схематично показана железная дорога из Нью-Йорка в Калифорнию с ответвлением, ведущим в Техас. Каждый символ формулы представлен одним вагоном. Поезд движется на запад (налево). Перед стрелкой каждый вагон должен останавливаться и узнавать, должен ли он двигаться прямо в Калифорнию, или ему нужно будет по пути заехать в Техас. Вагоны, содержащие переменные, всегда направляются в Калифорнию и никогда не едут в Техас. Вагоны, содержащие все прочие символы, должны перед прохождением стрелки узнавать о содержимом ближайшего вагона, отправившегося в Техас.
    В таблице показана зависимость ситуации от того, какой вагон отправился в Техас последним и какой вагон находится у стрелки. Первый вагон (помеченный символом ⊥) всегда отправляется в Техас.



    Числа соответствуют следующим ситуациям:
    1. Вагон на стрелке отправляется в Техас
    2. Последний вагон, направившийся в Техас, разворачивается и направляется в Калифорнию
    3. Вагон, находящийся на стрелке, и последний вагон, отправившийся в Техас, угоняются и исчезают
    4. Остановка. Символы, находящиеся на Калифорнийской ветке, представляют собой формулу в обратной польской записи, если читать слева направо
    5. Остановка. Произошла ошибка. Изначальная формула была некорректно сбалансирована

    После каждого действия производится новое сравнение вагона, находящегося у стрелки (это может быть тот же вагон, что и в предыдущем сравнении, а может быть следующий вагон), и вагона, который на данный момент последним ушёл на Техас. Этот процесс продолжается до тех пор, пока не будет достигнут шаг 4. Отметим, что линия на Техас используется как стек, где отправка вагона в Техас – это помещение элемента в стек, а разворот отправленного в Техас вагона в сторону Калифорнии – это выталкивание элемента из стека.
    Порядок следования переменных в инфиксной и постфиксной записи одинаков. Однако порядок следования операторов не всегда один и тот же. В обратной польской записи операторы появляются в том порядке, в котором они будут выполняться.

    Пример вычисления выражения в обратной польской записи
    Обратная польская запись идеально подходит для вычисления формул на компьютере со стеком. Формула состоит из n символов, каждый из которых является либо операндом, либо оператором. Алгоритм для вычисления формулы в обратной польской записи с использованием стека прост. Нужно просто прочитать обратную польскую запись слева направо. Если встречается операнд, его нужно пометить в стек. Если встречается оператор, нужно выполнить заданную им операцию.
    В качестве примера рассмотрим вычисление следующего выражения: (8+2*5)/(1+3*2-4). Соответствующая формула в обратной польской записи выглядит так: 825*+132*+4-/
    Число на вершине стека – это правый операнд (а не левый). Это очень важно дл операций деления, вычитания и возведения в степень, поскольку порядок следования операндов в данном случае имеет значение (в отличие от операций сложения и умножения). Другими словами, операция деления действует следующим образом: сначала в стек помещается числитель, потом знаменатель, и тогда операция даёт правильный результат. Отметим, что преобразовать обратную польскую запись в машинный код очень легко: нужно просто двигаться по формуле в обратной польской записи, записывая по одной команде для каждого символа. Если символ является константой или переменной, нужно вписывать команду помещения этой константы или переменной в стек, если символ является оператором, нужно вписывать команду выполнения это операции.

    P.S. Исходные коды вы, как всегда, можете скачать на моём сайте, пока он не ляжет под хабраэффектом.
    P.P.S. Теперь все могут написать свой калькулятор. С блэкджеком и скобками.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 71
    • +94
      • +16
        по моему горчица должна была быть на столе а не на соскиске: Р
        • –2
          Вы смеете усомниться в Randall Munroe? :)
          • +2
            не боги горшки обжигали =)
            • +5
              Ну вы поверните сосиску на -\pi/2 и будет счастье :)
              • 0
                ну вот понимаете же о чем я )))
                • +2
                  Вернее на -pi 2 /
                • +6
                  Боги обжигания горшков на вас обижаются. ©
          • 0
            А почему именно постфиксная запись? Чем префиксная хуже? ИМХО она более логична и проста для восприятия.
            • +3
              Потому что на момент получения оператора, операнды уже в стеке. :)
              * Хотя насчёт «интуитивной понятности» не могу не согласится)
              • –1
                Ну да, насчёт стека не спорю :) Спасибо за топик, вспомнил хоть, что в унивеситете учил.
            • +10
              Этот алгоритм вроде как преподают в любой нормальном вузе для программистов.
              • +15
                Не все на хабре закончили ВУЗ по специальности программист, но это не значит что им не будет интересно.
                • –2
                  Знать сабж по имени и не обязательно — не все же учились на программиста и зубрили названия алгоритмов — но реализовать его на практике сможет любой программист, когда приспичит распарсить строковые выражения.

                  Хотя я бы предпочёл префиксную запись и рекурсию по дереву, если бы писал калькулятор — интуитивно понятнее, как отметили выше — но я не привык вручную работать со стеком и экономить память, ассемблера лет десять не видел :)
                  • +6
                    Большинство программистов бинарное дерево реализовать не может…
                    • +4
                      Значит им повезло с работой, если они могут обходиться без этих знаний :) — мне приходится так или иначе делать эти деревья практически в каждом проекте и по многу раз — вот и сейчас я занимаюсь ни чем иным, как расширяю древнее приложение, прикручиваю возможность неким сущностям в приложении иметь дочерние сущности, и пытаюсь это всё красиво отобразить в рамках старого интерфейса.

                      Поступить на программера, что-ли… пусть меня научат всему тому, чем я занимаюсь последние годы…
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          Часть из них даже не знает что это такое :(
                      • –1
                        Ну начните тогда с объяснения сортировки пузырьком — всё-таки это более «плавное» погружение в среду, чем польская запись.
                      • +2
                        по моему инеженерам не программистам тоже =)
                        • 0
                          Не факт — Киевский политехнический институт, физтех — алгоритма не было. Я-то его еще в лицее писала, но это другая история.
                        • 0
                          У нас его давали на первом курсе, калькулятор был курсовой.
                          • +4
                            Я лично в школе разбирался с обратной записью. Замечу, что не в столице, не в областном центре и даже не в районном, а В ОБЫЧНОЙ СОВЕТСКОЙ ШКОЛЕ!!! На уроках информатики (или математики?) нас учили работать с программируемыми калькуляторами, типа этого:

                            • +3
                              У меня такой дома был. Ох как красиво он упал со шкафа.
                              Мне маленькому, для него лампу не продали в магазине.
                              Я был безумно обижен на продавца. Так хотел порадовать папу, что я тоже умею паять.
                            • 0
                              нам в школе давали. в 10ом.
                              • 0
                                вообщем-то не программистам тоже
                                • –7
                                  не только в вузе, но и в колледже. правда там его, алгоритм, называли венгерской нотацией.
                                  • +2
                                    Венгры это обратные поляки.
                                    • +4
                                      Да ну. Венгерская нотация — это совсем другая штука, соглашение об именовании переменных :) Особенно люто применяется в Microsoft (там, собственно, и зародилась)
                                      • 0
                                        Три года использую и только сейчас узнал что это «Венгерская нотация» :)
                                      • 0
                                        не, люди, я серьёзно. =) я действительно проходил этот алгоритм в колледже. и там его действительно называли венгерской нотацией.
                                    • –1
                                      Зачем исходные коды, если Вы рассказываете об алгоритме?
                                      • +2
                                        По опыту знаю, что многим будет просто лень реализовывать алгоритм самим.
                                        • +1
                                          А ещё сайт попиарить чуть-чуть хотите? :)
                                          • +2
                                            Ну… Можно и так сказать. Хотя это не самоцель)
                                      • +13
                                        Вы издеваетесь? следующими будут алгоритмы сортировки?
                                        • +10
                                          Вы будете удивлены, но я сам недавно столкнулся с программистом, который не знал сабжа. Причём довольно-таки неплохим специалистом. У всех бывают пробелы в образовании… =)
                                          • 0
                                            вообще странно это все
                                            у нас например все начинали писать свои калькуляторы именно с конвертера инфикстной записи в постфиксную
                                            • 0
                                              ну нереально же всё держать в голове, особенно те знания, которыми долгое время (годами) не пользуешься… сам польскую запись уже забыл. спасибо, мать ученья :)
                                              • +1
                                                Ну таким программистам надо не популярные статейки на Хабре читать, а проштудировать хотя бы пару университетских учебников по алгоритмам. Дело нехитрое.
                                              • +2
                                                После беглого просмотра Седжвика «Фундаметальные алгоритмы на С», раздел «Сортировка», глава «Быстрая сортировка», где представлены 7 (или 11, точно не помню) вариантов QuickSort, я бы не говорил о сортировке столь пренебрежительно.
                                                • +3
                                                  А ещё есть Кнут, который этому целый том посвятил…
                                                  • 0
                                                    Кнут — да. Но QuickSort у Седжвика разобран подробнее, с различными оптимизациями и хитростями.
                                              • +8
                                                На этом калькуляторе считалось тоже обратной записью.
                                                (2+2)*3 вводить как 3 В 2 В 2 + x

                                                • +6
                                                  Это мой первый ПК :-)
                                                  Памяти в них было мало и ОПЗ позволяла экономить драгоценные байты. Эх, было время, когда боролись за отдельные ячейки памяти :-)
                                                  • +1
                                                    Офисный ПК =)
                                                    • 0
                                                      А у меня такого не было и мне приходилось у знакомого правдами и неправдами выманивать (приходить к нему домой, выпрашивать на денек-другой), чтобы немного «покодить» :)
                                                      • 0
                                                        Я первое время ходил в Дворец Пионеров на кружок программируемых калькуляторов :-)
                                                    • +2
                                                      Что ж вы делаете?

                                                      Прямо слезы на глаза от его вида наворачиваются… Помню я с ним в крестики-нолики играл…
                                                      • –1
                                                        Одних «лунолётных» программ с десяток было (с мощным для тех времён «бэкстори»), а ещё и стратегии, и экономические симуляторы и много чего ещё :)
                                                        • 0
                                                          А я на нем в авиасим играл. FSX и X-Plane нервно курят в сторонке. :)
                                                        • 0
                                                          Да… оно… %)
                                                          • 0
                                                            Лучше «2 В 2 + B 3 x». Тут ведь стек всего-то на 4 элемента. В этом примере — не вылезет, а вообще — грабли :)
                                                          • +1
                                                            ех, помню лабы по трансляторам. Вроде именно перевод с польскую инверсную запись был самым большим гемороем…
                                                            • –2
                                                              круто, реально круто)!11
                                                              • 0
                                                                Как я намучался с этим, когда писал скрипты для nncron…
                                                                • 0
                                                                  Всегда завидовал тем, кто успел придумать \ изобрести \ запатентовать нечто крайне простое, вроде этой записи )
                                                                  • +1
                                                                    Ностальгия… Сам использовал ОПЗ при написании дипломной работы на тему «Пакет программ по численным методам». Вводилась формула в строковом виде, преобразовывалась в ОПЗ, ну и далее интегрировалась, дифференцировалась, решались дифуры.
                                                                    • НЛО прилетело и опубликовало эту надпись здесь
                                                                      • 0
                                                                        Почему-то вспомнил lisp и его префиксную запись операторов.
                                                                        • 0
                                                                          Лисп не из той оперы. В Лиспе есть скобки, а RPN как раз позволяет от скобок избавиться.
                                                                        • 0
                                                                          Форма с оператором между операндами называется инфиксной записью. Форма с оператором после операндов называется постфиксной, или обратной польской записью в честь польского логика Я. Лукасевича (1958), который изучал свойства этой записи.

                                                                          Не совсем верно. Лукасевич изобрел польскую нотацию (префиксную). На ее основе более чем через 30 лет была разработана обратная польская запись (постфиксная).
                                                                          • 0
                                                                            Судя по такому восторженному рассказу про RPN, вам наверняка должен понравиться язык Форт.
                                                                            • 0
                                                                              Хороший язык, красивый, помню даже сам для него «транслятор» (насколько это слово к нему применимо) «портировал» (лет через 10 только узнал, как это называется) с 8086 на 8080, жаль на практике у него применение очень ограниченно :(
                                                                              • 0
                                                                                У любого языка область применимости очень ограничена. Но знакомство с Фортом пллезно каждому, мозги неплохо прочищает.
                                                                                • 0
                                                                                  Планировщик задач для windows nnCron вроде как даже написан на Форте, и при этом скрипты для него синтаксис форта активно используют.
                                                                                  А мозги прочищает реально здорово.
                                                                                  • 0
                                                                                    Это, по-моему, единственный пример его широкого практического использования :(

                                                                                    Насчёт мозгов не скажу, это был мой третий язык после BASIC*MICRON* и ASSM*MICRON*, особенно заср… хм, запачкаться :) не успели
                                                                              • 0
                                                                                > В таблице показана зависимость ситуации…

                                                                                Я внимательно прочитал статью. И никак не могу понять, как составлена эта таблица? Вы приводите её как данность, но хотелось бы понимания, откуда она взялась.
                                                                                • 0
                                                                                  возьметесь написать преобразователь в ОПЗ не числового выражения, а строкового? ;-)

                                                                                  Элементами выступают не числа с операторами, а слова.

                                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.