Алгоритм Пинг-Понг или критика Обратной Польской Нотации

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

Источником описания ОПН будет описание из Лафоре Р.: Л29 Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2013. — 704 с, рекомендованное как наиболее популярное и адекватное по этому вопросу, впрочем как и по другим часто применяемым алгоритмам.

Ну то есть сравниваем разные алгоритмы с разной идеологией.

Для визуализации последовательности работы над формулой (ОПН) на стр.158 приведён следующий граф:

image

Уже здесь можно увидеть подстраивание алгоритма под неверное для человека свойство последовательного считывания символьной информации. Для человека более характерно приоритетное выделение фрагментов выражения и построение дальнейшей схемы расчётов по приоритетам этих фрагментов. Поэтому в данном случае схема будет выглядеть в реальности вот так:

image

Как видим, неверный исходный посыл на посимвольный разбор выражения приводит не только к искажению обработки инфиксной записи, но и существенно усложняют картину реального разбора сложных формул с множественными вложениями скобок. Ведь вторая схема (Рис1) и понятнее и существенно короче, чем представлено на Рис.4.15 анализируемого источника.

Далее я вынужден привести достаточно пространную цитату из источника, в которой «сову натягивают на глобус».
«Как видите, в процессе вычисления результата инфиксного арифметического выражения приходится перемещаться по выражению в прямом и обратном направлениях. Сначала слева направо читаются операнды и операторы. При накоплении информации, достаточной для применения оператора, вы начинаете двигаться в обратном направлении, «вспоминаете» два операнда и оператор и выполняете арифметическое действие. Если за оператором следует другой оператор с более высоким приоритетом или скобки, применение оператора откладывается. В этом случае сначала применяется следующий, более приоритетный оператор, а затем вы возвращаетесь обратно (влево) и применяете более ранние операторы.

Конечно, алгоритм для выполнения подобной обработки можно было бы запрограммировать напрямую, и все же, как уже говорилось ранее, проще сначала преобразовать выражение к постфиксной записи.» (конец цитаты)
Начнём с перемещения в прямом и обратном направлении. Дело в том, что апологеты ОПН обычно делают упор на последнем этапе расчётов, когда уже пересортированные символы сложены в стек и извлекаются оттуда подряд, что конечно же делает этот этап очень эффективным, вроде как. Но ведь, как помним работа по ОПН состоит из ДВУХ этапов (стр. 153):
«1. Преобразование арифметического выражения в другой формат, называемый постфиксной записью.

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

Однако давайте посмотрим внимательно на этап первый. Благо автор предоставляет для этого шикарную таблицу (стр. 153):

image

Больше всего мне понравилась последняя строчка. Вот расскажите, ради бога, как это можно здесь последовательно вытаскивать из СТЕКА и получать вменяемый результат. Система из двух стеков, отдельно для операндов и отдельно для операций, ещё будет работать, а вот с одним стеком…

Но речь даже не об этом. Сколько и каких сортировок нужно сделать, чтобы из инфиксной (привычной нам) записи сделать постфиксную? К чему так ломать нормальную человеческую логику студентов в угоду древнего метода? Боюсь даже представить как будет выглядеть, например, такая формула: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S). А у вас получилось представить это сходу?

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

Проиллюстрируем последовательность требуемых операций (ОПН) на небольшом примере.

image
Табл1. Порядок расчёта фрагмента формулы

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

У меня нет задачи пересказывать метод расчёта ОПН, поэтому те, кому особо интересно, могут прочитать о нём в первоисточнике, тем более что он действительно классно написан. Посему перейдём к методу (алгоритму) Пинг-Понг, анонсированному в названии статьи.

Сразу оговорюсь, методов (алгоритмов) распарсивания формул достаточно много. Можно назвать и метод рекурсивного спуска и методы построения деревьев и другие. Пинг-Понг мною в сети найден не был, хотя, так думаю, его используют достаточно часто. Почему он получил такое название станет ясно из иллюстраций.

Итак, переходим к разбору алгоритма. Начнём с некоторых определений для удобства изложения.

Приоритет – доминирование одной операции или группировки над другими. В алгоритме используются три приоритета: 0 – операции « ±»; 1 – операции «*/%»; 2 – группировка круглыми скобками «( )». Примечание: функции и работа с ними в данной статье не рассматриваются. Функции – просто отдельный слой, который не оказывает влияния на приоритетность выполнения операций.

Фрагмент – часть формулы, которая может быть передана для более низкоуровневого расчёта. То есть фрагментом является как часть формулы обрамлённая скобками и содержащая операции 0-го и 1-го уровней, так и тривиальный фрагмент, содержащий два операнда и знак операции между ними.

Для удобства иллюстрации будем использовать ту же формулу, которая была предложена выше для расчёта по ОПН: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W). Чтобы было более наглядно в процессе иллюстрации работы алгоритма я буду заменять буквы на цифры. Поехали.

Имеем строку формулы на входе.

image

Операнды вытаскиваются относительно знака операции, один слева другой справа. Последовательность операций внутри фрагмента напрямую зашита приоритетом последовательности обработки с замещением результатом. Вопросы унарного и бинарного « — » решаются внутри блока сложения/вычитания.

Так думаю, что здесь даже и не надо много разъяснений. Ну и так же понятно откуда название. Как видим, сортировки отсутствуют как класс, ограничений на длину формулы и количества вложенных групп — нет. Всё на уровне тривиальных поисков и замен. Чтобы не плодить обрывки строк, достаточно вместо String использовать StringBuilder (java), который позволяет трансформировать строку не плодя лишних сущностей. Ну а главное – это всё понятно на уровне простого интуитивного восприятия.

Для сравнения алгоритмов представим их в одинаковой нотации.

Алгоритм для ОПН взят из Wiki

image

Алгоритм Пинг-Понг

image

Таким образом алгоритм Пинг-Понг максимально приближен к человеческому восприятию и требует минимального количества ресурсов. Он также по минимуму требует анализа символов и процедур выбора решения, не требует буфера для сборки чисел из цифр.

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

Буду рад если кому-то этот алгоритм пригодится.
Поделиться публикацией
Похожие публикации
Ой, у вас баннер убежал!

Ну, и что?
Реклама
Комментарии 279
  • +9
    (n+u)*i*(d+u-b)^i-n*a/j*e(i+a)
    • 0
      Не понял. Это указание на какую-то ошибку или предложение что-то объяснить?
      На всякий случай — алгоритм тестировался на формулах типа: -2.5*(10+12)-(20.5+(2*(3/6-5)*2+10/5))+100+((10.2+12.8)*2/4-5+[log10|100|]*[sqrt|4|]+[pow|2;3|])
      • 0
        Мне кажется, что последнее выражение в скобках все-таки лишнее. Формула достаточно законченная и без нее.
        • 0
          Наверное вы правы. Просто я не понял предыдущего товарища.
          • +1
            Просто там написано «Ну и дубина же я» — читайте по именам переменных. :)
      • +3
        Никогда не нравилась Польская нотация… Я верю в то, что она годна на определённой стадии конструирования простейших вычислительных структур, а равно, и обучении штудентов именно этой стадии. Но единственное, что она делает — выносит разбор синтаксиса в мозг программисту, оставляя машине максимально тупое исполнение вычисления. Поэтому прослушать пол-лекции и сделать три упражнения, безусловно, полезно. Но в дальнейшем пусть этим занимается транслятор, а не мозг программиста. Одновременно я не вижу важного смысла критиковать польскую нотацию — это как критиковать символ интеграла или форму цифры «4». Они просто существуют и занимают не более часа человеческой жизни в глубоком детстве.
        • 0
          Целиком и полностью согласен.
          • 0
            Как по мне, так мозг программиста достаточно гибок, чтобы выражения сразу в программе писать в польской записи. Я так писал и никаких трудностей не испытывал.
            Наоборот:
            1) сокращается длина выражения, так как нет лишних символов в виде скобок, короче текст программы
            2) нет разночтений в приоритете операций, об этом просто не нужно даже помнить, очередность исполнения определяется стеком, а не типом операции.
            • 0
              1) сокращается длина выражения, так как нет лишних символов в виде скобок, короче текст программы

              Длина подаваемой на вход строки не может сократиться — какая есть, такая и есть. Или вы имеете ввиду формулы которые и так обрабатываются на этапе компиляции.
              2) нет разночтений в приоритете операций, об этом просто не нужно даже помнить, очередность исполнения определяется стеком, а не типом операции.

              Приоритетность операций определяется математикой. Какие могут быть разночтения?
              • 0
                Я говорю о том, что прямо в программе программист может писать в польской записи (ну если бы были такие языки, кроме форта).
                Например вот так:
                if( a b | )
                {
                c = a b d * +;
                }

                И как по мне — это достаточно удобно.
                • 0
                  В тексте программы вы можете писать как угодно — компилятор разберёт.
                  Ну а потом, здесь же никто никому ничего не навязывает. Вам удобно — здорово, пишите как удобно. Однако попробуйте всё же написать в ОПН конечное выражение предложенной в статье формулы: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W).
                  Ну и с посимвольным разбором естественно.
                  • +1
                    Те, кто пишет на форте никогда мысленно не представляют выражение в традиционном скобочном варианте, чтобы потом его разбирать. Они сразу в голове представляют себе выражение в стековом виде. Мозг легко к этому привыкает.
                    Конечно, если формула напечатана в книжке и ее нужно разобрать — и переписать в оп, ну может это и не просто.
                    • –2
                      (простите, но немного ехидно) Вам уже получилось написать ОПН для предложенной выше формулы?
                      • 0
                        .
                        • +1
                          А что в ней сложного?
                          A B C * D / + E F G H J 0 1 — * — I + L M N — * R — / S + * W * +
                          На вскидку.
                          • –3
                            «E F G H J 0 1 — * —» — ??? Разве отработает?
                            • 0
                              А с чего бы ему не отработать?
                              Из нуля вычитаем единицу — получаем -1 (я не стал придумывать литерал отрицательного числа).
                              Потом умножаем на него J, и следом вычитаем то, что получилось из H.
                              Вы никогда стековую машину что ли не писали?

                              Почему движок минусы на тире заменил — это не ко мне вопрос. Я разделил команды пробелами — для удобства.
                        • +3
                          У меня всю школу был калькулятор Мк-56 с польской нотацией… (а в институте мк-52 такой же). А вычисления которые надо было делать — выглядели чаще всего как-то так:
                          image
                          и записать это в виде bx24|a*c*-кореньb+_2/a/, было совершенно естественным и трудностей никаких не вызывало. Не скажу что я со своим калькулятором обращался медленнее, чем народ со своими «классическими», скорее наоборот, причём временами значительно, на длинных лабах — набегала наблюдаемая разница, но это возможно просто размер клавиш играл роль.
                          В статье — для честного сравнения на «входе» надо давать нормальные математические выражения с цепочками дробей и корней, не переведённые заранее в «скобочную» строчную форму, иначе получается что-то типа перевода удобных любимых круглых миль в вечно дробные километры.
                          Понятно, что учить студентов, по сути взрослых уже людей, заново арифметике — занятие неблагодарное, сама польская запись тут не при чём, люди 10-12 лет уже как до автоматизма довели «скобочную» запись, базовый по сути навык. Учили бы со школы наоборот — скобки бы вызвали бы точно такое же неприятие-отторжение.
                          соотв. утверждение, что линейная запись со скобочками чем-то предпочтительнее или быстрее чем польская нотация — вцелом некорректно — кто к чему привык…
                          … но, поскольку, подавляющее большинство населения сейчас «скобочники» — то пусть уж так и будет повсюду и нет острой необходимости в альтернативном стандарте (и неизбежных холиварах (мы в нём?)) иначе чем для кругозора и редких применений узкими специалистами.
                          Впрочем всё идёт к тому, что обе нотации в итоге останутся не у дел, а калькуляторы, а затем (не скоро да) и даже компиляторы будут понимать нормальную «бумажную» запись.
                          • 0
                            В статье не ставилась задача переучить кого-то. В первую очередь задачей было предложить более естественную альтернативу для изучения вопроса парсинга формул.
                            В статье — для честного сравнения на «входе» надо давать нормальные математические выражения с цепочками дробей и корней, не переведённые заранее в «скобочную» строчную форму, иначе получается что-то типа перевода удобных любимых круглых миль в вечно дробные километры.

                            Да пожалуйста: -2.5*(10+12)-(20.5+(2*(3/6-5)*2+10/5))+100+((10.2+12.8)*2/4-5+[log10|100|]*[sqrt|4|]+[pow|2;3|]). Могу что-нибудь посложнее, символов так на 300 и 20-тью вложенными на несколько уровней скобками. Имеет смысл?
                            Впрочем всё идёт к тому, что обе нотации в итоге останутся не у дел, а калькуляторы, а затем (не скоро да) и даже компиляторы будут понимать нормальную «бумажную» запись.

                            Вот здесь согласен полностью :)
                            • 0
                              Да пожалуйста: -2.5*(10+12)-(20.5+(2*(3/6-5)*2+10/5))+100+((10.2+12.8)*2/4-5+[log10|100|]*[sqrt|4|]+[pow|2;3|]).
                              нет. это УЖЕ переведённая в «скобочную» форму запись. Вы исходник дайте — как его мелом на доске пишут. И желательно осмысленную формулу из конкретных (жизненных) ситуаций.

                              И это… как бы обойтись без холиваров?.. Да, обратная польская запись без привычки корёжит мозг, есть такое дело, много раз наблюдал, я ж с этим не спорю…
                              • 0
                                А вот нет, не дам, поскольку строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.
                                И это… как бы обойтись без холиваров?..

                                Да я только ЗА. Просто, поскольку статья моя, считаю необходимым отвечать по возможности всем. Было бы здорово если бы просто выяснили неточности, ткнули носом в ошибки — и всё. Но так почему-то не получается.
                                • 0
                                  А вот нет, не дам, поскольку строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.

                                  Так дело-то в том, что можно трансформировать сразу в ОПН, без промежуточного скобочного вида. Это просто вопрос договорённости. Собственно, вам точно так же по аналогии с
                                  Да пожалуйста: -2.5*(10+12)-(20.5+(2*(3/6-5)*2+10/5))+100+((10.2+12.8)*2/4-5+[log10|100|]*[sqrt|4|]+[pow|2;3|]). Могу что-нибудь посложнее, символов так на 300 и 20-тью вложенными на несколько уровней скобками. Имеет смысл?

                                  можно предложить задачу перевести формулу из ОПН в инфиксную запись со скобками.
                                  • 0
                                    Так дело-то в том, что можно трансформировать сразу в ОПН, без промежуточного скобочного вида.

                                    Увы, не получится. Скобки тоже являются элементом алгоритма ОПН (открывающая скобка заносится в стек).
                                    можно предложить задачу перевести формулу из ОПН в инфиксную запись со скобками.

                                    Не получится. Поскольку уже потеряна значимая для инфиксной записи информация, то может возникнуть многовариантность результата. Особенно на одноприоритетных участках. Скобки выполняют дополнительную функцию фиксации внимания на фрагменте, выделения не арифметических, а смысловых групп. Вы не восстановите адекватно даже такое простое выражение как (A + B) — (C — D) из ABCD+_-_-
                                    • +2
                                      ОПН безскобочный!
                                      открывающая скобка заносится в стек

                                      Это цитата из алгоритма преобразования инфиксной записи в постфиксную.
                                      Вы не восстановите адекватно даже такое простое выражение как (A + B) — (C — D) из ABCD+_-_-

                                      потому, что вы не правильно написали… в ОПН это будет ABCD+-+
                                      • –1
                                        ОПН безскобочный!

                                        Ну вы же сами ниже согласились что и при преобразовании и при расчёте открывающая скобка используется. Иначе получается что сущность есть, а в названии мы её отрицаем.
                                        вы не правильно написали… в ОПН это будет ABCD+-+

                                        Возможно. Хотя насколько я понимаю там возможны варианты в зависимости от того, кто из последних операндов больше.
                                        Но ведь это всё уже не так уж и принципиально.
                                        • +2
                                          Преобразование != расчет. Это же два разных алгоритма! в ОПН НЕТ скобок. Незачем они там. Преобразование инфиксной записи в ОПН к ОПН не имеет НИКАКОГО отношения
                                          • –4
                                            Давайте просто согласимся что у нас с вами разные точки зрения на алгоритмы.
                                      • 0
                                        Увы, не получится. Скобки тоже являются элементом алгоритма ОПН (открывающая скобка заносится в стек).

                                        Причём тут алгоритм? Формулу из исходного вида (например, с доски) всё равно нужно (человеку) как-то перевести в строку. Общепринятым вариантом является инфиксная запись, но это просто вопрос соглашения.

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

                                        Не получится. Поскольку уже потеряна значимая для инфиксной записи информация, то может возникнуть многовариантность результата.

                                        Как это мешает перевести из ОПН в инфикс? Главное, чтобы функция та же самая была.
                                        • –1
                                          Формулу из исходного вида (например, с доски) всё равно нужно (человеку) как-то перевести в строку.

                                          Согласитесь что перевод с доски в строку — это уже другой алгоритм и мы здесь его не рассматривали исходно. Для перевода в инфиксную запись — это сгруппировать скобками числитель и знаменатель и трансформировать дробную черту в знак деления — всё. А для ОПН? (вопрос риторический)
                                          Главное, чтобы функция та же самая была.

                                          Вопрос в возможности представления одной постфиксной записи несколькими вариантами инфиксной.
                                          у меня предложение закончить эту интересную тему, как не совсем относящуюся к основной теме статьи.
                                          • 0
                                            Такое ощущение, что вы сравниваете не два вида записи (инфикс vs постфикс т.е. ОПН), а два алгоритма вычисления формулы по инфиксной записи. Это так? Тогда явно отметьте как-то в статье, а то вообще не понятно.

                                            В таком случае вполне ожидаемо, что есть более эффективный или простой алгоритм для непосредственного вычисления инфиксной записи, без перевода в ОПН. А вот сам вопрос выбора записи, в которой работать, это просто вопрос соглашения — и дело только в том, что мы все привыкли к инфиксной.
                                            • –1
                                              По большому счёту вы правы. Есть одинаковые вход и выход. Вопрос во внутренних подходах к обработке.
                                              Лично для меня ОПН показался слишком перегруженным с точки зрения понимания и стало жалко молодёжь.
                                              • 0
                                                Ну вот, а по статье (и комментариям, кстати) это вообще не ясно. Поэтому и много недопонимания тут в коментах — все (большинство) думают, что вы сравниваете вычисление выражений, представленных в ОПН и инфиксной записи (и тогда понятно, что по ОПН вычислить намного проще).
                                                • 0
                                                  Значит у меня получилось плохо донести основную мысль. Да, согласен, к таким вещам надо относится более внимательно. Критику учёл с благодарностью.
                                            • 0
                                              > А для ОПН?

                                              Вы не поверите, но то же самое. ОПН точно так же рекурсивно разбивается на блоки. замена блока (a op b) на блок (a b op) и обратно — чисто механическая.
                                      • 0
                                        строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.
                                        возможно в этом и проблема обучения — исходник уже конвертирован в машинно-читаемый, неудобный человеку для восприятия вид. я об том и реку — что если не конвертировать предварительно-промежуточно — то преобразование сложной формулы с доски/бумаги (а исходники формул для каких-либо вычислений обычно имеют именно такой вид) — что в «скобочную» запись, что в ОПН — примерно одинаковые по сложности/быстроте/удобству, дело лишь в привычке. А в вашем примере — для обучения (для работы это уже другой кейс) сейчас приходится вначале парсить в уме весьма неудобочитаемую белиберду, кракозябру кодировку-строкозапись, и уже потом её переводить в ОПН, держа в голове собственный стек скобок/приоритетов. Надеюсь вы не будете оспаривать, что нагляднсть плотно записанной строки сильно проигрывает нормальной математике (поэтому тот язык (математика) и был изобретён — «просто текста» — не хватало). А строки — что скобками, что польская — это вынужденный костыль посимвольного алфавитно-цифрового вода-вывода современной электроники… Вот ваша задача по постановке- это именно что (научиться) менять эти костыли/протезы/ходули/сапоги на ходу, вместо того, что бы одевать их в удобном месте глядя на изначальный, ничем не пожатый вид формул. Возможно поэтому и у студентов массовое неприятие — их учат на самом деле не тому, чему хотят научить, загружая мозги буссмысленной рутинной работой по парсингу закодированных строк.
                                        • –3
                                          Слушайте, а напишите формулу определенного интеграла в ОПН?
                                          • 0
                                            Спасибо минусанувшему в карму.
                                            Что ж, придется пояснять, раз люди не понимают, человек написал:
                                            преобразование сложной формулы с доски/бумаги (а исходники формул для каких-либо вычислений обычно имеют именно такой вид) — что в «скобочную» запись, что в ОПН — примерно одинаковые по сложности/быстроте/удобству, дело лишь в привычке.
                                            Однако сложные формулы на доске при обучении стремятся постоянно к усложнению и уже к концу средней школы выходят за границы тех простых операторов, которые вечно в примерах ОПЗ присутствуют. Вот и хотелось понять границы того, как человек это воспринимает.
                                            • 0
                                              Спасибо минусанувшему в карму.
                                              (не, этот минус не мой (я свой на вас даааа-вно истратил, (не помню конкретно, но думаю, что за дело (я _только_ за деструкцию дискуссии минусю (прямые оскорбления и т.п.))))),
                                              Я в институте с доски или тетради как правило считал на калькуляторе ощутимо быстрее, чем мои товарище по парте на своих «классических». Причём чем навороченнее были расчёты — тем больше разница была. Но, возможно, там дело было в чём-то ещё — размере/удобстве клавиш/дисплея калькулятора, его быстродействии или т.п. (В т.ч надо помнить, что эти калькуляторы был программируемые, поэтому прямо сравнить никак — любая повторяющаяся больше чем дважды формула — проще забить программу, тем боле, что она — почти просто макрос нажатий. Поэтому формула интеграла конкретной функции — заведом будет выигрышна, ибо забита в программу и дальше только вводи значения агрумента. На сейчас, естесственно это неактуально)
                                              Отдельным плюсом было то, что народ очень быстро перестал просить калькулятор попользоваться, ибо первый же вопрос «а где тут „равно“?»… «а скобки где?» поврегал их в ступор и уныние… и в общем, смотрели как на шамана…
                                              Я с ходу не нашёл картинки-примера большой сложной формулы — не думал что обсуждение будет столь острым-длинным — слишком много вопросов смешал в кучу автор (сама запись, её простота/удобство, сложность освоения (напр пузырьковый алгоритм прост — но он не самый удачный, а БПФ просто чудо, но на пальцах не объяснить), сложность алгоритма перевода из ()записи в ОПН и сложность понимания этого алгоритма студентами… причём автор эти вопросы тасует как хочет в любом камменте, интересно в каком ВУЗ он препод?
                                              • 0
                                                Забыл добавить — в тех калькуляторах было ограничение на глубину стека — всего 4, что иногда здорово мешало. При этом поведение стека было хитрым — если число попало на дно стека — то при «всплывании» дублировалось, на дне тоже оставаясь, что иногда здорово помогало. Соотв. это была не «чистая» ОПН, но тем не менее — полностью ВСЕ расчёты в ВУЗе я делал в ней — и это было скорее удобнее, чем коллегам в обычных. Но — повторюсь — у меня опыт с ней с младшей школы (как и у них — в «скобочной» (в коей у меня, в общем тоже, ибо в тетрадке надо было-таки писать в оной)). И, конечно — единичный пример — не статистика, и соотв толком не аргумент — думаю, это само собой очевидно.
                                                • +1
                                                  почему не аргумент? нормальный аргумент, что можно не сильно медленнее, как минимум, перегонять в другой вид, главное уметь.
                                                  просто большинство здесь под пред/постфискной нотацией исключительно алгебру понимают… видимо кого-то в тупик вопрос поставил…
                                                  ps. я тут уже отвечал, данные способы записи не без скобочные, просто скобки не нужны для операторов с известной арностью и их опускают (унарные и бинарные же в основном в простой математике операторы и функции), если используются операторы а-ля сумм(х1; х2;...; хn) — скобки сразу возникают.
                                                • 0
                                                  -2.5*(0.03+0.02)*(-12.752+(-25.5656/-5.1249)-(2*4-5*2+10/5))+100+((25+(6*12/3*(-1)-((((9-7)*3.5+(-1)*(4+5+11-24/2-(5*3/5+42)+1287/5.4)-20)-20)+4.2)*47)-60+(((10.2+12.8)*2/4-5+[log10|100|]*[sqrt|9|]+[pow|2,3|])+10))+(10*0.02+12/0.02)+(60*20/30+10))+(-102.5478+52.1422) — держите. На ней тестировался алгоритм.
                                                  Ну и да, автор не препод. :)
                                            • 0
                                              Надеюсь вы не будете оспаривать, что нагляднсть плотно записанной строки сильно проигрывает нормальной математике

                                              Нет не буду. Вы правы в том, что язык математики не зря был изобретён. Возражу в том, что перевод нормального математического языка в скобочную (инфиксную) запись, что в запись ОПН одинаков по сложности. Всё же ОПН много сложнее.
                                              Вот ваша задача по постановке- это именно что (научиться) менять эти костыли/протезы/ходули/сапоги на ходу, вместо того, что бы одевать их в удобном месте глядя на изначальный, ничем не пожатый вид формул.

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


                                      Стив возняк (кстати, поляк по происхождению) об обратной польской нотации:
                                      Заголовок спойлера

                                      • +3
                                        А почитать не завезли? Кино оставьте тем, кто читать не умеет.
                                • +2
                                  Длина подаваемой на вход строки не может сократиться — какая есть, такая и есть.

                                  Может: "(a + b) * c" vs "a b + c *". Обычно принято между операторами ставить пробелы, и в этом случае их и слева и справа по 4 штуки. А вот скобок справа нет.


                                  Приоритетность операций определяется математикой. Какие могут быть разночтения?

                                  У чего приоритет больше — у >> или | или ^? Это не имеет отношения к математике и может различаться от языка к языку. Я такие моменты не всегда помню, операторов куча, иногда лучше скобки поставить.


                                  P.S. я не фанат польской нотации, но Ваши аргументы неубедительны.

                                  • 0
                                    Да ладно, если на входе строка сразу в ОПН, то это уже не вопрос выбора алгоритма, но обычно всё же исходная строка представлена в инфиксной (обычной) форме.
                                    Ваши аргументы неубедительны.

                                    А вот это уже предмет для разговора. Здесь хотелось бы поподробнее.
                                    • +6

                                      Идея раз — польскую нотацию надо знать. Она простая (никаких приоритетов, просто стек и операции) и очень близка к тому, как это выражение потом будут вычислять. (например, байткод jvm или питона содержит команды типа "загрузить/удалить из стека" и "взять с вершины N элементов, сделать что-то и положить результат обратно на стек").


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


                                      Классический алгоритм читает вход посимвольно, и это даёт интересные возможности:


                                      • он может обрабатывать большие файлы, последовательно читая их байт за байтом без необходимости держать весь файл в оперативной памяти.
                                      • его можно компоновать с другими обработчиками — например, собрать цепочку из алгоритмов — первый убирает комментарии из строки, второй — парсит числа и операции (чтобы потом не развлекаться сборкой числа из цифр), третий — преобразует в постфиксную нотацию, четвёртый тут же вычисляет результат.

                                      Классический алгоритм не использует рекурсию. Вся память, что ему нужна — стек. Проще уже некуда.

                                      • –3
                                        Спасибо за развёрнутый комментарий, теперь есть объект для рассмотрения.
                                        Идея раз — польскую нотацию надо знать.

                                        — согласен.
                                        Она простая (никаких приоритетов, просто стек и операции)

                                        Это не так. Сложность выражения и приоритеты определяются самим выражением, а не преобразованной уже его формой. Просто ОПН все сложности перекладывает на этап сортировки, который почему-то иногда пытаются забыть. Процесс вычислений тоже не так линеен, вспоминаем про скобки (открывающая лежит в стеке операций) и про приоритеты операций во фрагменте.
                                        Теперь про алгоритм пинг-понг. Он воспринимается проще, но в нём есть фатальный недостаток — он постоянно бегает туда-сюда по строке и меняет её.

                                        Бегает туда-сюда Пинг-Понг не более чем ОПН, ветвлений меньше, основная операция «поиск по маске» более удобна для конвейера. Единственно когда просмотр начинается с начала строки — это при послойном (по приоритетам операций) расчёте. В ОПН, в принципе, тоже самое, только метаний побольше.
                                        вместо стека для алгоритма ОПН в пинг-понге используется чтение-запись из памяти размером со входные данные.

                                        Это так только на этапе выделения фрагмента. По размеру Вы сильно ошибаетесь как в отношении Пинг-Понг так и в отношении ОПН. И там и там используется метод высечения фрагментов. Только в ОПН он вроде как скрытый, а в Пинг-Понг явный.
                                        Чтение символа (каждого символа) в ОПН происходит из памяти, затем этот символ долго крутят, чтобы положить в нужное место, причём, в зависимости от предыстории, можно уйти и на расчёт и на укладывание в стек и на реверсивный расчёт фрагмента.
                                        В Пинг-понг каждый символ не крутится в логике и считывается только при непосредственной потребности и то, не посимвольно для чисел и операций, а смысловой группой. Считывание операции и операндов из стеков, а затем укладывание результата снова в стек, может несколько и быстрее, но ничем не отличается от считывания операндов и операции из строки и замены фрагмента на результат расчёта.
                                        может обрабатывать большие файлы, последовательно читая их байт за байтом без необходимости держать весь файл в оперативной памяти.

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

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

                                        Пинг-Понг как-то тоже рекурсию не использует. Вся память, которая ему нужна это входная строка (в ОПН тоже есть) и строка фрагмента (в ОПН стек, вернее ДВА стека). К тому же он избавлен от опасности переполнения стека.
                                        Так что пока преимуществ ОПН, извините, пока не наблюдаю. Скоростная работа со стеком в ОПН с лихвой компенсируется накладными расходами на посимвольной аналитике, как в режиме сортировки, так и в режиме расчётов.
                                        Проще уже некуда.

                                        Я не утверждаю, поверьте, что ОПН плохой алгоритм, но по поводу его простоты, как мне кажется, Вы сильно преувеличиваете.
                                        • +8

                                          Вас так и будут минусовать до тех пор, пока вы не начнёте отделять постфиксный способ записи выражений (ОПН) и алгоритм перевода из инфиксной записи в постфиксную.


                                          Процесс вычислений тоже не так линеен, вспоминаем про скобки (открывающая лежит в стеке операций) и про приоритеты операций во фрагменте.

                                          Это не так. В постфиксной записи нет скобок, как нет и приоритетов операций. Значения просто кладутся в стек, операции просто забирают из него необходимое количество аргументов и кладут обратно результат. Вы снова путаете алгоритм преобразования записи (Сортировочная станция) с тривиальным алгоритмом вычисления постфиксного выражения.


                                          Главное преимущество: выполнить преобразование инфиксной записи в постфиксную можно на этапе компиляции, тогда на этапе выполнения нагрузка сильно снизится. Это будет работать даже в интерпретируемых языках, поскольку парсинг исходного кода и преобразование во внутренний байткод производится один раз, а вычисление выражения — хоть миллион в цикле.

                                          • –2
                                            Спасибо за корректное указание на мои ошибки. Действительно, рассматривая алгоритмы как целостное получение результата от одинаковых исходных данных я несколько упустил специфику терминологии.
                                            Что интересно, так это то, что в комментариях отсутствует пошаговый разбор алгоритма на ОПН. Утверждения есть, а разбора нет. И это говорит о многом, например, о неполном понимании его работы «нажми на кнопку — получишь результат». И это не только в комментариях, но и в достаточно серьёзной литературе.
                                            Если у Вас есть время, то можем в режиме диалога попробовать устранить нестыковки и противоречия, которые присутствуют в описании алгоритма и его реальном пошаговом исполнении.
                                            • +2
                                              пошаговый разбор алгоритма на ОПН

                                              Какого алгоритма? Алгоритма сортировочной станции или алгоритма вычисления выражения в ОПН?

                                              • –1
                                                В статье присутствует пошаговое исполнение ОПН, правда на небольшом кусочке, который был достаточен для демонстрации. Также в статье присутствует полный расчёт той же формулы на Пинг-Понге.
                                                В данном случае я имел ввиду алгоритм получения конечного результата через преобразование в ОПН. Так что объедините вместе обозначенные вами части и получите результат. Всё просто.
                                                • 0

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

                                                  • –2
                                                    Вы сейчас серьёзно?
                                                    Я уже попросил одного из комментаторов разделить эти алгоритмы между собой на примере из классической книги по алгоритмам, указанной в начале статьи. Можете тоже попробовать.
                                                    Не надо мантр, давайте что-нибудь сделаем реальное.
                                                    • +3

                                                      Да, я серьёзно. Оригинальный алгоритм сортировочной станции не включает в себя вычисление выражения, только его преобразование. Затем уже полученное выражение при необходимости и возможности вычисляется. То, что Лафоре придумал что-то другое, пусть останется на его совести.

                                                    • 0
                                                      С какой целью это необходимо было разбирать в комментариях пошагово, если уже давно описано в литературе?

                                                      Чтобы те, кто прочитает этот комментарий могли самостоятельно сделать выводы по многим другим комментариям.
                                                      А про литературу тоже очень интересно. Достаёшь классика и показываешь, а в ответ:«это всё фигня — в топку».
                                                      • +1
                                                        Классика — это Ахо и Ульман. Вирт. Кнут — тоже классика. А этого вашего Лафоре я в первый раз вижу. Допускаю, что книжка хорошая, но либо вы из неё не то процитировали, либо он что-то не так написал, не знаю. Только та картинка, которую вы изволили дать в статье, равно как и ваши пояснения, алгоритма «сортировочной станции» никак не поясняет. Википедию лучше читайте, ей богу.
                                                        • –2
                                                          Ну зря Вы так.
                                                          Картинка, кстати хорошая и правильная для реализации «сходу».
                                                          За книжки спасибо.
                                                          • +2
                                                            valerar, вы действительно невнимательно читали Лафоре. Преобразование в постфикс и вычисление постфикса у него разделено, и иначе быть и не могло, ибо Лафоре разбирает классические алгоритмы, а не придумывает какие-то собственные. Вы это точно заметите, если пролистаете его книгу ниже картинки, которую запостили — там приведена картинка, поясняющая вычисление уже постфиксного выражения и далее — код по теме, который вам бы явно не мешало изучить.
                                                          • +1
                                                            Лафоре чист от ереси (цитирую добытую из недр харда его «Структуры данных и алгоритмы в Java»):
                                                            "Преобразование инфиксной записи в постфиксную (...) никакие арифметические операции в нем не выполняются. Конечной целью является не вычисление результата, а расположение операторов и операндов в новом формате постфиксной записи."
                                                            Так что автор статьи что-то не так понял. Вероятно, его смутило то, что Лафоре посвятил пару страниц сравнению того, как происходит «человеческое» вычисление выражения, записанного в традиционном для математики виде и того, как происходит преобразование в постфикс — и, кстати, Лафоре приводит это как раз для того, чтобы доказать новичку то, что ничего чуждого человеческому восприятию в постфиксе на самом деле нет.
                                                  • +1
                                                    И это говорит о многом...

                                                    Не делайте далеко идущих выводов. Алгоритм преобразования инфиксной записи в постфиксную банальность. Я сам использовал его, за свою жизнь, раз пять (может больше, я не считал). Кстати, похожий на ваш алгоритм пинг-понга придумал мой сокурсник при схожих обстоятельствах. А я ему объяснял алгоритм на двух стеках. Это было годах в 90-ых. Не знаю, что вы именно к этому так прицепились?
                                                    • 0
                                                      Использовать и понимать несколько разные вещи. Мы часто в жизни используем то, что до конца не понимаем. Поэтому и предложено приверженцам одного стека и простоты суммарного алгоритма преобразование — расчёт провести натурный эксперимент на бумаге. Такие эксперименты сильно прочищают мозги.
                                                      • 0

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

                                                        • –1
                                                          Когда в мозгах отсутствует понимание ни тесты ни профилирование не спасают, тогда только карандаш и бумага.
                                                          • 0
                                                            Всего лишь по этой фразе уже можно судить, насколько человек далек от программирования.
                                                        • 0
                                                          Я не использую то чего не понимаю. Например, я не использую БПФ. Собственно, мне и не требуется.
                                                          • 0
                                                            Хорошая позиция, солидарен.
                                                            Ну а я не пишу о том, что не понимаю. Когда нам удастся сблизить наши языки (физики-химики), скорее всего мы поймём что оба говорили об одном и том же.
                                        • 0
                                          > Как по мне, так мозг программиста достаточно гибок, чтобы выражения сразу в программе писать в польской записи.

                                          В форте вся программа записывается в ОПН. Главное свойство ОПН — конкантенативность. Если Х — программа в ОПН и y — программа в опн, то xy — программа в ОПН. Ну и стековая семантика.
                                      • 0
                                        AB+C-

                                        Больше всего мне понравилась последняя строчка. Вот расскажите, ради бога, как это можно здесь последовательно вытаскивать из СТЕКА и получать вменяемый результат. Система из двух стеков, отдельно для операндов и отдельно для операций, ещё будет работать, а вот с одним стеком…


                                        Достаёте из стека два операнда, запоминаете. Достаёте из стека операцию. Применяете к операндам. Записываете результат в как первый операнд. Достаёте из стека ещё один операнд. Достаёте операцию и применяете к операндам.
                                        • –2
                                          Имелась ввиду строчка: A+B*(C — D/(E + F)) преобразованная в «ABCDEF±*+ » — именно она является последней в приведённой таблице.
                                          Ну а подоставать из стека, можно предварительно туда положив, я оставляю вам. Думаю на уровне реальных действий вам будет о-о-очень интересно.
                                          • +1
                                            Удалил — фигня получилась
                                            • +1
                                              Если уже до такого преобразовали, то посчитать в чем проблема-то?

                                              Есть очередь «A B C D E F + / — * +» и пустой стек. Алгоритм очень простой: достаем по одному из очереди. Если достали число — положили в стек. Если достали «операцию» — вынули из стека два числа, применили «операцию», положили обратно в стек. Когда очередь кончилась в стеке лежит результат вычисления.

                                              Что интересного в этих реальных действиях?

                                              Вообще ОПН imho удобнее применять сразу при разборе выражения «A + B * (C — D / (E + F))». Тогда просто два стека нужно использовать. Один для чисел, второй для операций. Общий алгоритм немного сложнее естественно будет. Но результат тот же.
                                              • –1
                                                Хорошо. Давайте я попробую по ваше методе.
                                                Участники: 1. очередь (FIFO) содержит ОПН; 2. стек (LIFO) пустой
                                                Примечание: Это уже не схема с одним стеком, часто отстаиваемая в комментариях
                                                Расчёт:
                                                1.«A B C D E F + / — * +»
                                                2. А — достали из очереди; число — положили в стек; (А) — состояние стека
                                                3. B — достали из очереди; число — положили в стек; (АB) — состояние стека
                                                4. C — достали из очереди; число — положили в стек; (АBC) — состояние стека
                                                5. D — достали из очереди; число — положили в стек; (АBCD) — состояние стека
                                                6. E — достали из очереди; число — положили в стек; (АBCDE) — состояние стека
                                                7. F — достали из очереди; число — положили в стек; (АBCDEF) — состояние стека
                                                8. + — достали из очереди; операция — вытащили E и F = r1 в стек (АBCDr1) — состояние стека
                                                9. / — достали из очереди; операция — вытащили r1 и D = r2 в стек (АBCr2) — состояние стека
                                                10. "- " — достали из очереди; операция — вытащили r2 и C = r3 в стек (АBr3) — состояние стека
                                                11. * — достали из очереди; операция — вытащили r3 и B = r4 в стек (Аr4) — состояние стека
                                                12. + — достали из очереди; операция — вытащили r4 и А = r5 в стек (r5) — состояние стека
                                                Умышленно прошёл всё, чтобы было видно: во-первых, работа возможно только с 2-мя выходными объектами (это любителям рассуждать про один стек, не вам); во-вторых, у нас получается три этапа:1. преобразование в ОПН 2. перенесение операндов в стек 3. непосредственно расчёт формулы. Это уже любителям рассказывать про всё за один проход.
                                                Согласен с Вами, использовать сразу два стека сильно эффективнее (часть расчётов происходит сходу, но тогда придётся работать со скобками, а это уже больно сердцу «безскобочников».
                                                Кстати, Вы очень замечательно заменили первичное хранилище ОПН очередью. Вы первый кто вообще произнёс это слово в обсуждении.
                                                Не знаю как у Вас, а у меня точно складывается ощущение, что большая часть комментирующих плохо представляют работу алгоритмов на ОПН. И не понятно что с этим делать… :((
                                                • +1
                                                  Во первых входная очередь токенов — это вход (FIFO), он будет всегда вне зависимости от нотации и алгоритма, так что при расчете используется всё-таки один стек (LIFO).
                                                  работа возможно только с 2-мя выходными объектами
                                                  Но у вас же он один (стек LIFO) в котором и лежит первым элементом r5 (результат вычисления)…
                                                  у нас получается три этапа:1. преобразование в ОПН
                                                  Обсуждали не раз токенизация нужно при любом алгоритме и любой нотации, но входную строку преобразовывать в очередь (FIFO) можно «на лету» без перемещения по строке
                                                  2. перенесение операндов в стек 3. непосредственно расчёт формулы
                                                  на самом деле это один этап. Эта ошибка у вас произошла из-за достаточно простой входной строки попробуйте что-нибудь типа A B + C D + * (расписал ниже) тогда складывание опендов и вычисление будет на одном этапе.
                                                  часть расчётов происходит сходу, но тогда придётся работать со скобками, а это уже больно сердцу «безскобочников».
                                                  ну вы же сами вот только что… без скобок… В инфиксной записи это выражение: ((F+E)/D -C)*B+A вам ведь в ОПН не понадобились скобки.

                                                  плохо представляют работу алгоритмов на ОПН

                                                  Вы уже близко подошли к пониманию этих алгоритмов. Это похвально. Большая разница между тем, что у Вас было в начале

                                                  Но вообще вы уже ближе подошли к пониманию алгоритма расчета ОПН
                                                  • –2
                                                    Я понимаю ваше желание защитить коллег. Вопрос: оно того стоит? Я ни на кого не собираюсь нападать, никого не собираюсь обижать, но факт есть факт — большинство слабо понимают работу ОПН. Я даже на примере корзинок пытался объяснять… Вот у Вас нет проблем с ОПН и мы можем спокойно разговаривать уже просто о технических вопросах.
                                                    Во первых входная очередь токенов — это вход (FIFO), он будет всегда вне зависимости от нотации и алгоритма, так что при расчете используется всё-таки один стек (LIFO).

                                                    «Входная очередь» — это вы имеете ввиду непосредственно для расчёта, насколько я понял. Здесь пожалуй не соглашусь. Ну не нужен мне Пинг-Понге никакой массив и я не формирую ни очередей ни стеков. Так что не везде нужны такие сущности.
                                                    входную строку преобразовывать в очередь (FIFO) можно «на лету» без перемещения по строке

                                                    А вот тут не понял. Перемещение по какой строке вы имеете ввиду?
                                                    на самом деле это один этап. Эта ошибка у вас произошла из-за достаточно простой входной строки попробуйте что-нибудь типа A B + C D + * (расписал ниже) тогда складывание опендов и вычисление будет на одном этапе.

                                                    Есть такая интересная штука в нашем сознании — опускание значимых деталей на уровне «это очевидно». Ваш пример не очевиден. Так понимаю, A B + C D + * — это очередь с ОПН. Ну и забираем А и куда? То есть ничего не изменилось по отношению к разобранному нами примеру — кладём в стек. То есть этапы по определению не могут быть совмещены, они могут быть только фрагментированы.
                                                    ну вы же сами вот только что… без скобок… В инфиксной записи это выражение: ((F+E)/D -C)*B+A вам ведь в ОПН не понадобились скобки.

                                                    Здесь они не были нужны, поскольку отсутствовали расчёты на лету и я не стал влезать в процесс самого формирования ОПН.
                                                    Кстати, очень интересный эффект трансформации формулы с которой мы работали. Исходная, в самом начале, выглядела так: «A + B * (C — D / (E + F))», после трансформации «A B C D E F + / — * +», а сейчас, очевидно после восстановления, превратилась в ((F+E)/D -C)*B+A. Просто интересное наблюдение.
                                                    Однако вернёмся. При вычислениях на лету мы вынуждены ориентироваться на не до конца разобранную формулу и можем рассчитывать только однозначно определённые фрагменты. "(" не позволяет однозначно определить завершённость фрагмента, который можно было бы уже рассчитать, поэтому мы помещаем её в стек операций — она будет служить отсечкой реверса при возвращении к прямому анализу символов исходной строки. ")" — фиксирует завершённость фрагмента и позволяет произвести его расчёт. Так что здесь просто немного разные алгоритмы. Хотя, блин, у меня не выходит из головы как вы преобразовались тогда без скобок. Да и что-то последовательность операций встречная по отношению к операндам в очереди. Ладно, это потом.
                                                    Вы уже близко подошли к пониманию этих алгоритмов. Это похвально. Большая разница между тем, что у Вас было в начале

                                                    Спасибо, конечно, за комплимент, но я, с вашего позволения, его отклоню. Где-то может язык и терминология сблизились. Я начал лучше понимать используемый вами язык. А моё видение и понимание вначале достаточно полно показано в статье. И вроде пока не изменилось с тех пор.
                                                  • +1
                                                    Очередь на входе — это все же входящие данные. Очередь в данном случае — удобная абстракция, не более. Это может быть, например, массив, в котором лежат готовые токены. Или поток. Не суть. Здесь важно только то, что придет подготовленная постфиксная запись выражения.

                                                    На выходе же мы имеем только одну структуру данных — стек.

                                                    По вашим пунктам:
                                                    1. Преобразование в постфиксную запись из инфиксной — это подготовительная операция. Если ее проводить самостоятельно, то нужен будет только один стек для той самой «сортировки» операций по приоритетам. На входе в каком-то виде выражение (пусть набор символов тот же). Токенизация тут же происходит. На все требуется один проход по исходным данным.
                                                    2. Перенесение операндов в стек в полном составе происходит очень редко. В данном случае вы предложили вырожденный случай, а не «усредненный» пример. В общем случае в стеке одновременно не будут находиться вообще все операнды.
                                                    3. Непосредственный расчет как раз за один проход и делается. Как раз об этом я написал в конце. Видимо не очень понятно, виноват. Попробую еще раз.

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

                                                    Мне кажется Вы не совсем верно уловили основное назначение ОПН как таковой. Про один стек и проход везде упоминают только и исключительно для подготовленной постфиксной записи. Эта самая запись и называется ОПН. Ее подготовка — это отдельная операция, да. Основное применение — интерпретаторы и компиляторы. Выражение, написанное программистом, переводится в ОПН и, грубо говоря, таким остается в коде. На этапе выполнения вместо переменных подставляются реальные значения и быстро, в один проход, с одним стеком, выражение вычисляется.
                                                    • –3
                                                      Ну вроде как я начинаю понимать ваш язык. Радует.
                                                      С учётом преамбулы с пунктами 1.2.3. нормально. Наше видение здесь совпадает.
                                                      А вот это меня заинтересовало.
                                                      На этапе выполнения вместо переменных подставляются реальные значения и быстро, в один проход, с одним стеком, выражение вычисляется.

                                                      Смотрим.
                                                      Участники:1. участок памяти с откомпилированной формулой 2. массив конкретных значений переменных формулы 3. стек для получения результата (пока пустой)
                                                      1. Переменные из кода инициализируются конкретными значениями из массива и помещаются в стек.
                                                      2. из кода последовательно вытаскиваются операции, которые производят вычисления с двумя первыми операндами стека, результат в стек (цикл)
                                                      То есть, если я всё правильно понял, каждый операнд участвует в процессе три раза:1. инициализация переменной 2. помещение в стек 3. извлечение из стека для операции.
                                                      То есть, если отбросить сами операции, то получаем три прохода по одному операнду, без всяких преобразований. Это я к тому, что даже на самом эффективном этапе это всё же не один проход, что в принципе не возможно. Ну если не считать только проходом инкремент счётчика индекса в строке.
                                                      Извините, это у меня в голове ещё продолжается параллельно дискуссия с другими комментаторами.
                                                      Для меня было важно вот это
                                                      Основное применение — интерпретаторы и компиляторы.

                                                      Это снимает многие вопросы к дискуссии по этой статье. Спасибо.
                                                      • +3
                                                        Основное применение — интерпретаторы и компиляторы.
                                                        Это снимает многие вопросы к дискуссии по этой статье. Спасибо.

                                                        Вам об этом сегодня целый день говорили. Только вы не хотели вникать в комментарии.

                                                        • –4
                                                          Ну не целый день, тут Вы уж загибаете, но раз пять помню. :)
                                                        • +3
                                                          каждый операнд участвует в процессе три раза:1. инициализация переменной 2. помещение в стек 3. извлечение из стека для операции. То есть, если отбросить сами операции, то получаем три прохода по одному операнду

                                                          Эти действия совершаются не на этапе парсинга выражения, а на этапе вычисления, так что машина работает уже не со строками или регулярными выражениями, а с числами, которые представлены в удобном ей виде. Так что это три элементарных присваивания, которые выполнятся быстрее чем Ваш «очень быстрый» поиск по маске.
                                                          Основное применение — интерпретаторы и компиляторы.
                                                          Это снимает многие вопросы к дискуссии по этой статье. Спасибо.

                                                          Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.
                                                          • –2
                                                            Да конечно же я согласен что на этом этапе всё сильно быстрее. Просто, как настоящий зануда, прицепился к количеству проходов и всё.
                                                            Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.

                                                            В образовании, особенно для школьников. Ну у меня лично надо было что-то сыну подбросить. Заинтересовался он программированием и начал строить свой калькулятор. Я просмотрел кучу всякого и в итоге решил сделать сам. Ну так, чтобы, если что спросит, можно было адекватно объяснить.
                                                            Ну а по применению Пинг-Понга, с моей точки зрения, можно попробовать на длинных сложных формулах, которые нельзя заранее откомпилировать и где может потребоваться контроль промежуточных результатов расчётов. В нём удобно всякие контрольные точки ставить. Можно приспособить к разбору иерархических смысловых групп, если они имеют соответствующее обрамление (в части разбора по скобкам он не имеет контекстной зависимости. Как-то так. Вы меня застали в расплох, я об этом ещё не думал. Ему (алгоритму) от роду дней сорок, а реализации меньше месяца.
                                                            • +3
                                                              на длинных сложных формулах, которые нельзя заранее откомпилировать
                                                              Вроде выяснили, что ОПН будет эффективнее во всех смыслах кроме понимания ( субъективно для Вас ).
                                                              где может потребоваться контроль промежуточных результатов расчётов. В нём удобно всякие контрольные точки ставить.
                                                              Несложно реализовать и в ОПН, и в деревьях.
                                                              Можно приспособить к разбору иерархических смысловых групп, если они имеют соответствующее обрамление
                                                              Не очень понимаю, о чем вы, но звучит как задача, которая решается деревьями.
                                                              В образовании, особенно для школьников.
                                                              Но если в будущем он неприменим, зачем тратить время школьника?
                                                              Вы меня застали в расплох, я об этом ещё не думал.
                                                              Это неправильная стратегия разработки алгоритмов. Алгоритмы нужно придумывать не для того, что бы они были, а для решения реальных задач.
                                                              • –4
                                                                Вроде выяснили, что ОПН будет эффективнее во всех смыслах кроме понимания ( субъективно для Вас ).

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

                                                                Всё можно реализовать уже существующими способами. Развитие идёт тогда, когда начинают, по той или иной причине, искать альтернативные пути.
                                                                Не очень понимаю, о чем вы, но звучит как задача, которая решается деревьями

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

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

                                                                Он и решил задачу для которой был предназначен. Причём полностью и без тяжёлых последствий воздействия ОПН на голову и психику. А то, что я не рассматривал возможности применения в сфере промышленного программирования — это вопрос второй или дальше.
                                                                • +3
                                                                  > Пока не выяснили, по прежнему считаю что посимвольный разбор строки с большим количеством логики на длинных сложных формулах не обладает очевидной эффективностью.

                                                                  Как сложность и длина формулы влияет на разбор в ОПН, если время разбора в ОПН зависит только от длины формулы, причем линейно?

                                                                  Вы не предполагайте, просто рассмотрите ОПН и ваш алгоритм на какой-нибудь реальной формуле и посчитайте операции.
                                                                  • –1
                                                                    А может сделаем так.
                                                                    Вы апологет ОПН — отлично.
                                                                    Берём одинаковую формулу на входе; определяем инструмент (с вас и общедоступный); запускаем и обмениваемся результатами.
                                                                    Ещё раз я в курсе еффективности алгоритмов на ОПН, в курсе что разные алгоритмы ОПН дадут разную производительность, предполагаю (отсутствует точная информация) что под ОПН на современном железе есть аппаратные и программные ускорители, не может не быть, поскольку живёт долго и является доминантой в направлении. Однако готов провести такой эксперимент. Вот только писать для ОПН — увольте.
                                                                    • +1
                                                                      > Однако готов провести такой эксперимент.

                                                                      Отлично, проводите.
                                                                      • 0

                                                                        Так я вам ниже ровно это и предложил. Берите примеры исходников("формул", по-вашему), реализуйте велосипед, который их сможет вычислить (на выходе всегда одно значение), и давайте сравним.

                                                                    • 0
                                                                      Причём полностью и без тяжёлых последствий воздействия ОПН на голову и психику

                                                                      Ну, психам и не придётся программировать. А нормальные люди от ОПН никак не страдают.
                                                  • 0
                                                    Таким образом алгоритм Пинг-Понг максимально приближен к человеческому восприятию и требует минимального количества ресурсов.

                                                    А теперь представьте себе строку длинной в один миллион символов и сто тысяч пар скобок.
                                                    Хвост строки придется перемещать столько же раз.

                                                    • –3
                                                      представьте себе строку длинной в один миллион символов и сто тысяч пар скобок.
                                                      Хвост строки придется перемещать столько же раз.

                                                      Представил. Если формула конечна и помещается в памяти, то проблем не вижу.
                                                      Ну и не понял причём тут хвост строки. Строка укорачивается по мере расчёта фрагментов замещением фрагмента на рассчитанное значение. Как раз в этом отличий в алгоритмах нет.
                                                      • 0

                                                        Если вам на вход подадут строку ((a+b)+c)+d+...+z999.
                                                        То вы предлагаете создать строку (12+с)+d+...+z999.
                                                        Потом строку 18+d+...+z999.
                                                        Таким образом придется копировать кусок d+...+z999 в памяти несколько раз.
                                                        А значит выражение должно занимать меньше половины свободной памяти, если его можно менять.
                                                        Если выражение менять нельзя, то ограничения ещё сильнее.

                                                        • 0
                                                          Не совсем так. Я выделю сначала фрагмент (a+b). рассчитаю и заменю, затем то же самое с (12+с). Затем просто считается вся остальная формула. Но в этом-то смысле алгоритмы практически не отличаются. В ОПН происходит тоже самое. Копировать многократно строку я как-то особого смысла не вижу. Так что требования по памяти в обоих алгоритмах практически не отличаются. А вот переполнение стеков в предложенной вами конструкции миллион символов и сто тысяч скобок очень сильно вероятно.
                                                          • +1

                                                            Замена фрагментов в строке — очень дорогая операция. Строка представляет собой массив из символов, которые хранятся подряд без промежутков. Соответственно, заменяя (a+b) на 12 в начале строки, вы вызываете перемещение в памяти всего, что находится после, чтобы заполнить появившийся промежуток. И так на каждый этап вычисления. StringBuilder предотвращает выделение дополнительной памяти под фрагменты строк, но не работу по перемещению данных. (В .NET StringBuilder немного умнее и хранит строку в виде блоков, так что избыточное копирование ограничено размером блока, но никуда не девается).


                                                            В итоге вы экономите небольшой объём памяти под стек ценой большого количества дополнительной работы для процессора.

                                                            • 0
                                                              Замена фрагментов в строке — очень дорогая операция.
                                                              Если при чтении сразу писать в связанный список. Замена — переписать значение первого элемента и в ссылку на следующий записать значение ссылки из последнего элемента, которые заменяются?
                                                              • 0
                                                                Кэш на вас обидится. Лучше дек взять.
                                                                • 0
                                                                  Вообще, мне было нужно реализовывать считывание формул c max min +-*() с возможностью вложений, 6 переменными и произвольными числами из одного txt, а потом из другого txt брать собственно кучу вариантов значений этих переменных и для каждого произвести однотипный расчет.
                                                                  Я подумал над ОПЗ, но решил просто рекурсией в духе данного пинг-понга (да-да, велосипед), предварительно в массив поместив.
                                                                  Хотя, согласен, ОПЗ было бы проще — один раз формулу расковырял при помещении в структуру и дальше просто подставляй значения… Но так как велосипед исключительно был на поиграться для себя — я боялся что потом будет трудно вспоминать что к чему в случае необходимости его подправить (ну там расширить количество функций)

                                                                  Но меня оправдывает то, что все мои попытки экономить меркли на фоне необходимостью работать с ООо через оле… )
                                                                  А вопрос по сути — просто из интереса, а как еще можно было этот велосипед соорудить)
                                                                  • 0
                                                                    А вопрос по сути — просто из интереса, а как еще можно было этот велосипед соорудить)

                                                                    Если я правильно понял, то в вашей задаче формулы статичны и изменяются только переменные. В таком случае, ну так сходу с тяжёлой головой, отдать формулы на откуп компилятору — пусть сам разбирается, а потом, в процессе работы скармливать значения переменных упорядоченным массивом. Даже если формул несколько. достаточно помнить только кому какой массив подсунуть.
                                                                    • 0
                                                                      Если я правильно понял, то в вашей задаче формулы статичны и изменяются только переменные.
                                                                      Неа, формулы и переменные забираются из разных файлов в начале расчета.
                                                                      Условно: есть полуфабрикат, к нему привязаны формулы и какие-то параметры его самого как толщина, состав материалов и пр (так что в любом случае так что данные в любом случае разбирать).
                                                                      Подается список деталей прямоугольных с 6 размерами (длина и ширина заготовки, промежуточные и готовые), надо рассчитать комплектующие для его изготовления.
                                                                      Формулы уровня «max(min(X3,Y3),100)+40», "(X1+100)*1.2", периодически могут меняться.
                                                                      • 0
                                                                        Я не совсем понял конечный результат расчёта.
                                                                        надо рассчитать комплектующие для его изготовления.

                                                                        Это не результат. Ну хотя бы потому, что существует конструкторская документация в которой все комплектующие на изделие определены и описаны, даже если изделие может иметь разные массо-габаритные характеристики.
                                                                        Если вам интересно, давайте посмотрим на уровне логики.
                                                                        Про статичность формул. У меня почему-то сложилось впечатление что у вас есть некоторый набор формул, фиксированный, с помощью которых (комбинируя состав которых) вы получаете требуемый результат. То есть сами формулы не изменяются, а становятся фрагментами некоторой общей в той или иной комбинации.
                                                                        • 0
                                                                          Ну хотя бы потому, что существует конструкторская документация в которой все комплектующие на изделие определены и описаны, даже если изделие может иметь разные массо-габаритные характеристики.
                                                                          Это и было для расчета конструкторской документации. Причем внутренней, на изготовление деталей.
                                                                          Про статичность формул. У меня почему-то сложилось впечатление что у вас есть некоторый набор формул, фиксированный, с помощью которых (комбинируя состав которых) вы получаете требуемый результат.
                                                                          я даже почти реальные примеры привел. Первая формула была: «берем минимальный из габаритов детали, но не менее 100, увеличиваем на 40»; вторая «расход материала равен длина плюс припуск на отрез и всё это с коэффициентом 1,2». То есть урезанный набор операторов +-*, функции макс и мин, возможность группировать.

                                                                          «Формулы» на входе — уравнения расчетов, на выходе получаем габариты заготовок. Формулы меняются время от времени из-за изменения технологий или используемых материалов (далеко не каждый день). Список деталей каждый раз новый.
                                                                          • 0
                                                                            Это и было для расчета конструкторской документации. Причем внутренней, на изготовление деталей.

                                                                            Ну вот Вы и стали упорядочивать мои мозги по вашей задаче :)
                                                                            «Формулы» на входе — уравнения расчетов, на выходе получаем габариты заготовок. Формулы меняются время от времени из-за изменения технологий или используемых материалов (далеко не каждый день). Список деталей каждый раз новый.

                                                                            Становится ещё немного понятнее.
                                                                            Уточните ещё пожалуйста кто запускает эти расчёты и какая ваша связь с такими людьми как разработчика программы
                                                              • –2
                                                                Ну да… Я тоже про это подумал. Как-то более-менее объективно оценить насколько эта операция будет забирать на себя ресурсы у меня получилось только чисто логически. Однако, сокращение интеллектуальных операций при работе с каждым символом может скомпенсировать эти затраты. Специализировано этим вопросом не занимался, поэтому ничего внятного сказать не могу.
                                                      • +2
                                                        Больше всего мне понравилась последняя строчка. Вот расскажите, ради бога, как это можно здесь последовательно вытаскивать из СТЕКА и получать вменяемый результат. Система из двух стеков, отдельно для операндов и отдельно для операций, ещё будет работать, а вот с одним стеком…

                                                        Мне кажется, Вы не вполне правильно понимаете, как такое вычисляется. Предполагается, что арифметическое выражение в ОПН лежит в памяти (каждый операнд и операция в отдельной ячейке), а не в стеке. И преимущество ОПН именно в том, что все выражение в стек класть не надо. Алгоритм очень простой, читаем выражение из памяти слева направо:
                                                        1. Если встретилось число, кладем его в стек;
                                                        2. Если встретилась операция, достаем с вершины стека операнды для нее, вычисляем, результат кладем в стек.
                                                        Когда чтение выражения окончено, на вершине стека лежит его результат. Это очень экономный и быстрый алгоритм, в стеке лежит необходимый минимум данных: только результаты промежуточных вычислений, и никаких скобок и операций там нет.
                                                        • –3
                                                          Вы не вполне правильно понимаете, как такое вычисляется. Предполагается, что арифметическое выражение в ОПН лежит в памяти (каждый операнд и операция в отдельной ячейке), а не в стеке.

                                                          Извините, но арифметическое выражение лежит в наборе символов определяемых как «строка». И я нигде не говорил о том, что всю строку кладут сразу в стек. ОПН — это посимвольный разбор строки с кучей выборов как действовать в зависимости от предыдущего символа. И даже не одного, минимум трёх: предыдущая операция, предыдущий символ (формирование чисел из цифр), счётчик скобок.
                                                          1. Если встретилось число, кладем его в стек;

                                                          В строке нет чисел, там есть цифры (символы). Так что чтобы собрать число из отдельных цифр, ну если только у вас не односимвольные числа, то перед помещением в стек число ещё собрать надо.
                                                          2. Если встретилась операция, достаем с вершины стека операнды для нее, вычисляем, результат кладем в стек.

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

                                                          И это утверждение достаточно спорно. Во-первых, на КАЖДЫЙ символ навешана куча логики. Во-вторых, работа со скобками никуда не девается. Более того она просто откладывается до закрытия скобкой фрагмента. Ну и т.д…
                                                          Попробуйте реализовать свои утверждения на листе бумаги и с карандашом хотя бы на двух уровнях вложения скобок и вещественными операндами. Полагаю, получите искреннее удовольствие.
                                                          • +2
                                                            Тоже не совсем так. Если вновь прибывшая операция приоритетнее предыдущей, то мы обязаны её положить в стек без каких-либо вычислений. Ну и другие нюансы.

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

                                                            • 0
                                                              Да, похоже вы правы.
                                                              Проблему со сборкой чисел можно решить на другом слое.

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

                                                              Моя позиция такая: заставлять программиста писать сразу в ОПН — это либо глупость, либо суровая необходимость, когда нет достаточно умного компилятора, способного сделать это самостоятельно. Кстати, еще если пишешь на ассемблере, иметь представление об ОПН полезно. Для машины ОПН (не строка! а нормально подготовленное выражение в памяти, как я выше описал) — это оптимальная нотация, поэтому она часто используется при трансляции/компиляции и поэтому нет причин эту нотацию забывать.

                                                              При этом полностью согласен с Вами и комментатором выше, что обучать разбору выражений на примере ОПН — это извращение. Обучаться надо на том, что ближе к человеческой логике, а ОПН — это дополнение для разминки мозгов и широты кругозора. Кому-то же предстоит и компиляторы писать, пусть единицам.
                                                              • 0
                                                                Рад что мы пришли к согласию :)
                                                          • 0
                                                            Я не понял, что в результате делает алгоритм автора — вычисляет выражение?
                                                            Потому что алгоритм, с которым он сравнивает, названный "Алгоритм для ОПН взят из Wiki" и картинка под ним, выражение как раз не вычисляет, он служит для преобразования инфиксной нотации в постфиксную.

                                                            И алгоритм вычисления выражения по строке в программах обычно мало полезен, потому что интерпретировать строку каждый раз для вычисления затратно. Поэтому делают компиляцию выражения в машинные структуры, где вопросы приоритета, порядка вычисления и хранения промежуточных результатов уже решены и выражены в последовательности вызова нужных операций.
                                                            • 0
                                                              Я не понял, что в результате делает алгоритм автора — вычисляет выражение?

                                                              Да, оба алгоритма вычисляют математическое выражения. Вход у обоих одинаков, как и выход. Разница в подходе к процессу.
                                                              «Алгоритм для ОПН взят из Wiki» и картинка под ним, выражение как раз не вычисляет, он служит для преобразования инфиксной нотации в постфиксную.

                                                              Там показан полный цикл расчёта по первой скобке (4 операнда и 3 операции внутри скобок). Показывать более длинный фрагмент смысла не имело. Конечный результат расчёта фрагмента — «r3».
                                                              Компиляция действительно решает все вопросы с математическими выражениями напрямую зашитыми в коде, но не решает задачи где надо получить результат из полученой из вне строки с заранее неизвестным составом операндов и операций.
                                                              • 0
                                                                В алгоритме ОПН это вы добавили:

                                                                В оригинальном алгоритме преобразования в вике этого нет, там четко разделены алгоритмы вычисления и преобразования.

                                                                но не решает задачи где надо получить результат из полученой из вне строки

                                                                А такая задача в программировании, в отрыве от прекомпиляции, еще существует? В тех программах, где я встречал ввод произвольного выражения и его вычисления, обычно выражение сначала полностью парсится до попытки его вычисления. И это правильно, т.к. «А» может быть вызовом функции, делающей что-то еще. Если у вас синтаксически неправильное выражение, то ваш алгоритм часть выражения (и часть функций) выполнит, а часть нет — как бы это не то, что ожидается от компьютера.
                                                                • 0
                                                                  Да, похоже. Но алгоритм как-то надо было завершить, пусть и в упрощённой форме.
                                                                  В тех программах, где я встречал ввод произвольного выражения и его вычисления, обычно выражение сначала полностью парсится до попытки его вычисления.

                                                                  Ну а как вы будете его парсить отдельно от вычислений, в дерево раскладывать?
                                                                  Если у вас синтаксически неправильное выражение, то ваш алгоритм часть выражения (и часть функций) выполнит, а часть нет — как бы это не то, что ожидается от компьютера.

                                                                  Это одинаково для обоих алгоритмов. Некорректности приходится ловить не только во входной строке, но и возникающие в результате расчётов.
                                                                  • 0
                                                                    Это одинаково для обоих алгоритмов. Некорректности приходится ловить не только во входной строке, но и возникающие в результате расчётов.

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

                                                                    В вашем алгоритме такой проверки нет, вычисление начинается сразу со чтения первой переменной.

                                                                    Ну а как вы будете его парсить отдельно от вычислений, в дерево раскладывать?

                                                                    Да, представьте себе. Потому что кроме вычисления мне нужна и информация о задействованных переменных. Например, здесь на Python.

                                                                    import ast
                                                                    
                                                                    def parseSource(src):
                                                                        def parseFunc(expr, names):
                                                                            # Парсим выражение
                                                                            m = ast.parse(expr)
                                                                            # Получим список уникальных задействованных имен
                                                                            varList = list(set([ x.id for x in ast.walk(m) if type(x) == ast.Name]))
                                                                            # Найдем их позиции в грамматике
                                                                            indexes = [ names.index(v) for v in varList ]
                                                                            lam = 'lambda %s: %s' % (','.join(varList), expr)
                                                                            return (indexes, eval(lam), lam)
                                                                    
                                                                    • 0
                                                                      Нет, это не одинаково даже для алгоритмов в вашем представлении. В первом алгоритме есть строчка, перенесенная из вики «В стеке должны были остаться только символы операторов». Там еще есть продолжение "; если это не так, значит в выражении не согласованы скобки.". То есть здесь мы имеем контрольную точку проверки выражения на синтаксическую целостность, проверка выполняется до начала вычисления.

                                                                      В вашем алгоритме такой проверки нет, вычисление начинается сразу со чтения первой переменной.

                                                                      Ну в первом алгоритме только оценочное суждение: «должны были остаться» — это не фиксация этапа проверки.
                                                                      В представленном алгоритме так же не выделяется этап проверки парности скобок, хотя он присутствует и да, до начала разбора строки. Но так же не присутствует проверка деления на ноль, хотя такая ситуация может просто возникнуть в процессе вычисления. Но я считал важным показать сам принцип, а не обвесы вокруг. Возможно в этом я и не прав.
                                                            • 0
                                                              > Но речь даже не об этом. Сколько и каких сортировок нужно сделать, чтобы из инфиксной (привычной нам) записи сделать постфиксную?

                                                              Никаких сортировок делать не надо. Преобразование в ОПН выполняется за единственный проход элементарно — если перед нами число, то оставляем его на месте. Если конец строки — выписываем операции из стека. Если перед нами операция — выводим из стека операции <= приоритета, кладем операцию на стек.
                                                              • –3
                                                                Никаких сортировок делать не надо.

                                                                Простите, а «сортировочная станция» это тоже я придумал? (подражание известной фразе из к/ф «Кавказская пленница»)
                                                                Преобразование в ОПН выполняется за единственный проход элементарно

                                                                Чтобы не спорить бессмысленно вот вам формула: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W). Давайте разберём на её примере. Начало разбора приведено в статье. И просто посчитаем количество условий ветвления алгоритма в зависимости от предыдущей информации (даже не одного символа). Меня хватило только на одну скобку, может у вас получится лучше. Заодно посмотрим количество возвратов (метаний).
                                                                • 0

                                                                  Простите, вы этот алгоритм "сортировочной станции" видели? Он же элементарный. И сложность O(n).
                                                                  В стек заносятся только операторы и скобка. Можно немного модифицировать — повышать приоритет операторов после "(" и понижать обратно после ")", тогда в стек заносится пара (оператор, приоритет).
                                                                  Возвратов вообще нет и не может быть.

                                                                  • –3
                                                                    Ну я даже в статье привёл пример его работы, вообще-то. Я что-то неправильно отразил в его работе?
                                                                    Он же элементарный. И сложность O(n).

                                                                    А вот тут есть вопросы. Сколько-сколько условий и предусловий в нём учитывается.
                                                                    Вы сами попробуйте чуть усложнить формулу и сами всё увидите. Особенно когда введёте вещественные числа и множественные вложенные скобки.
                                                                    • 0

                                                                      Действительно, из книжки взято нечто странное.
                                                                      Сам алгоритм занимает что-то около 100 строк, есть на вики.
                                                                      Пример разбора 3*(4+5):
                                                                      1) читаем 3. число => выводим.
                                                                      2) читаем *. стек пуст => в стек.
                                                                      3) читаем (. в стек.
                                                                      4) читаем 4. выводим.
                                                                      4) читаем +. на вершине стека "(", значит "+" в стек.
                                                                      5) читаем 5. выводим.
                                                                      6) читаем ). очищаем стек до "(" включительно. выводим +.
                                                                      7) читаем "конец". очищаем стек, выводим все операторы что там были (*).
                                                                      Вроде бы, всё.
                                                                      Если усложнять строку — число шагов всё равно зависит линейно от числа лексем строки.

                                                                      • –2
                                                                        Ну вот мы, похоже, и договорились :)
                                                                  • +1
                                                                    > Простите, а «сортировочная станция» это тоже я придумал?

                                                                    Да, это вы придумали.

                                                                    > Давайте разберём на её примере.

                                                                    Давайте

                                                                    (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W)
                                                                    (A+BC*/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W)
                                                                    (A+BC*D/)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G/(H-J(-1)*+I)-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G/(HJ(-1)*-+I)-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G/(HJ(-1)*-I+)-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/-L*(M-N)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/-L*(MN-)-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/-L(MN-)*-R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*--R)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*-R-)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*-R-)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*-R-)+S)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*-R-)S+)*W)
                                                                    (ABC*D/+)+(E-F*((G(HJ(-1)*-I+)/L(MN-)*-R-)S+)W*)
                                                                    (ABC*D/+)+(E-F((G(HJ(-1)*-I+)/L(MN-)*-R-)S+)W**)
                                                                    (ABC*D/+)+(EF((G(HJ(-1)*-I+)/L(MN-)*-R-)S+)W**-)
                                                                    (ABC*D/+)(EF((G(HJ(-1)*-I+)/L(MN-)*-R-)S+)W**-)+

                                                                    ABC*D/+EFGHJ(-1)*-I+/LMN-*-R-S+W**-+

                                                                    Обратите, кстати, внимание, насколько последняя строка проще оригинала! Благодаря конкантенативности не нужно считать скобки и структура выражения стала гораздо понятнее. Ну и само выражение короче. И вычислить его гораздо проще (если цифры на место подставить то вычисление в ОПН я произведу гораздо быстрее чем вы в оригинале).