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

[AlexXYZ]

(n+u)*i*(d+u-b)^i-n*a/j*e(i+a)

[valerar]

Не понял. Это указание на какую-то ошибку или предложение что-то объяснить?
На всякий случай — алгоритм тестировался на формулах типа: -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|])

[sshmakov]

Мне кажется, что последнее выражение в скобках все-таки лишнее. Формула достаточно законченная и без нее.

[valerar]

Наверное вы правы. Просто я не понял предыдущего товарища.

[tongohiti]

Просто там написано «Ну и дубина же я» — читайте по именам переменных. :)

[EndUser]

Никогда не нравилась Польская нотация… Я верю в то, что она годна на определённой стадии конструирования простейших вычислительных структур, а равно, и обучении штудентов именно этой стадии. Но единственное, что она делает — выносит разбор синтаксиса в мозг программисту, оставляя машине максимально тупое исполнение вычисления. Поэтому прослушать пол-лекции и сделать три упражнения, безусловно, полезно. Но в дальнейшем пусть этим занимается транслятор, а не мозг программиста. Одновременно я не вижу важного смысла критиковать польскую нотацию — это как критиковать символ интеграла или форму цифры «4». Они просто существуют и занимают не более часа человеческой жизни в глубоком детстве.

[valerar]

Целиком и полностью согласен.

[nckma]

Как по мне, так мозг программиста достаточно гибок, чтобы выражения сразу в программе писать в польской записи. Я так писал и никаких трудностей не испытывал.
Наоборот:
1) сокращается длина выражения, так как нет лишних символов в виде скобок, короче текст программы
2) нет разночтений в приоритете операций, об этом просто не нужно даже помнить, очередность исполнения определяется стеком, а не типом операции.

[valerar]

1) сокращается длина выражения, так как нет лишних символов в виде скобок, короче текст программы

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

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

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

[nckma]

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

И как по мне — это достаточно удобно.

[valerar]

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

[nckma]

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

[valerar]

(простите, но немного ехидно) Вам уже получилось написать ОПН для предложенной выше формулы?

[Zenitchik]

А что в ней сложного?
A B C * D / + E F G H J 0 1 — * — I + L M N — * R — / S + * W * +
На вскидку.

[valerar]

«E F G H J 0 1 — * —» — ??? Разве отработает?

[Zenitchik]

А с чего бы ему не отработать?
Из нуля вычитаем единицу — получаем -1 (я не стал придумывать литерал отрицательного числа).
Потом умножаем на него J, и следом вычитаем то, что получилось из H.
Вы никогда стековую машину что ли не писали?

Почему движок минусы на тире заменил — это не ко мне вопрос. Я разделил команды пробелами — для удобства.

[impetus]

У меня всю школу был калькулятор Мк-56 с польской нотацией… (а в институте мк-52 такой же). А вычисления которые надо было делать — выглядели чаще всего как-то так:

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

[valerar]

В статье не ставилась задача переучить кого-то. В первую очередь задачей было предложить более естественную альтернативу для изучения вопроса парсинга формул.

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

Да пожалуйста: -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-тью вложенными на несколько уровней скобками. Имеет смысл?

Впрочем всё идёт к тому, что обе нотации в итоге останутся не у дел, а калькуляторы, а затем (не скоро да) и даже компиляторы будут понимать нормальную «бумажную» запись.

Вот здесь согласен полностью :)

[impetus]

Да пожалуйста: -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|]).

нет. это УЖЕ переведённая в «скобочную» форму запись. Вы исходник дайте — как его мелом на доске пишут. И желательно осмысленную формулу из конкретных (жизненных) ситуаций.

И это… как бы обойтись без холиваров?.. Да, обратная польская запись без привычки корёжит мозг, есть такое дело, много раз наблюдал, я ж с этим не спорю…

[valerar]

А вот нет, не дам, поскольку строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.

И это… как бы обойтись без холиваров?..

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

[chersanya]

А вот нет, не дам, поскольку строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.

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

Да пожалуйста: -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-тью вложенными на несколько уровней скобками. Имеет смысл?

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

[valerar]

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

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

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

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

[jetexe]

ОПН безскобочный!

открывающая скобка заносится в стек

Это цитата из алгоритма преобразования инфиксной записи в постфиксную.

Вы не восстановите адекватно даже такое простое выражение как (A + B) — (C — D) из ABCD+_-_-

потому, что вы не правильно написали… в ОПН это будет ABCD+-+

[valerar]

ОПН безскобочный!

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

вы не правильно написали… в ОПН это будет ABCD+-+

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

[jetexe]

Преобразование != расчет. Это же два разных алгоритма! в ОПН НЕТ скобок. Незачем они там. Преобразование инфиксной записи в ОПН к ОПН не имеет НИКАКОГО отношения

[valerar]

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

[chersanya]

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

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

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

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

Как это мешает перевести из ОПН в инфикс? Главное, чтобы функция та же самая была.

[valerar]

Формулу из исходного вида (например, с доски) всё равно нужно (человеку) как-то перевести в строку.

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

Главное, чтобы функция та же самая была.

Вопрос в возможности представления одной постфиксной записи несколькими вариантами инфиксной.
у меня предложение закончить эту интересную тему, как не совсем относящуюся к основной теме статьи.

[chersanya]

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

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

[valerar]

По большому счёту вы правы. Есть одинаковые вход и выход. Вопрос во внутренних подходах к обработке.
Лично для меня ОПН показался слишком перегруженным с точки зрения понимания и стало жалко молодёжь.

[chersanya]

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

[valerar]

Значит у меня получилось плохо донести основную мысль. Да, согласен, к таким вещам надо относится более внимательно. Критику учёл с благодарностью.

[Druu]

> А для ОПН?

Вы не поверите, но то же самое. ОПН точно так же рекурсивно разбивается на блоки. замена блока (a op b) на блок (a b op) и обратно — чисто механическая.

[impetus]

строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.

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

[impetus]

Спасибо минусанувшему в карму.

(не, этот минус не мой (я свой на вас даааа-вно истратил, (не помню конкретно, но думаю, что за дело (я _только_ за деструкцию дискуссии минусю (прямые оскорбления и т.п.))))),
Я в институте с доски или тетради как правило считал на калькуляторе ощутимо быстрее, чем мои товарище по парте на своих «классических». Причём чем навороченнее были расчёты — тем больше разница была. Но, возможно, там дело было в чём-то ещё — размере/удобстве клавиш/дисплея калькулятора, его быстродействии или т.п. (В т.ч надо помнить, что эти калькуляторы был программируемые, поэтому прямо сравнить никак — любая повторяющаяся больше чем дважды формула — проще забить программу, тем боле, что она — почти просто макрос нажатий. Поэтому формула интеграла конкретной функции — заведом будет выигрышна, ибо забита в программу и дальше только вводи значения агрумента. На сейчас, естесственно это неактуально)
Отдельным плюсом было то, что народ очень быстро перестал просить калькулятор попользоваться, ибо первый же вопрос «а где тут „равно“?»… «а скобки где?» поврегал их в ступор и уныние… и в общем, смотрели как на шамана…
Я с ходу не нашёл картинки-примера большой сложной формулы — не думал что обсуждение будет столь острым-длинным — слишком много вопросов смешал в кучу автор (сама запись, её простота/удобство, сложность освоения (напр пузырьковый алгоритм прост — но он не самый удачный, а БПФ просто чудо, но на пальцах не объяснить), сложность алгоритма перевода из ()записи в ОПН и сложность понимания этого алгоритма студентами… причём автор эти вопросы тасует как хочет в любом камменте, интересно в каком ВУЗ он препод?

[impetus]

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

[valerar]

-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) — держите. На ней тестировался алгоритм.
Ну и да, автор не препод. :)

[valerar]

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

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

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

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

[zugr]

Заметная разница набегала ПМК над обычными калькуляторами в связи с тем что: во-первых в стеке у него аж 4 числа можно хранить, против одной иногда двух вложенных скобочек в обычных калькуляторах(если вообще были таковые); во-вторых количество регистров памяти вообще аж 15 шт, против 1 иногда 2!

[YemSalat]

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

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

Заголовок спойлера

[Zenitchik]

А почитать не завезли? Кино оставьте тем, кто читать не умеет.

[lgorSL]

Длина подаваемой на вход строки не может сократиться — какая есть, такая и есть.

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

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

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

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

[valerar]

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

Ваши аргументы неубедительны.

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

[lgorSL]

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

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

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

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

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

[valerar]

Спасибо за развёрнутый комментарий, теперь есть объект для рассмотрения.

Идея раз — польскую нотацию надо знать.

— согласен.

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

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

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

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

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

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

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

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

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

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

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

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

Проще уже некуда.

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

[valerar]

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

[valerar]

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

[valerar]

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

[valerar]

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

Чтобы те, кто прочитает этот комментарий могли самостоятельно сделать выводы по многим другим комментариям.
А про литературу тоже очень интересно. Достаёшь классика и показываешь, а в ответ:«это всё фигня — в топку».

[GlukKazan]

Классика — это Ахо и Ульман. Вирт. Кнут — тоже классика. А этого вашего Лафоре я в первый раз вижу. Допускаю, что книжка хорошая, но либо вы из неё не то процитировали, либо он что-то не так написал, не знаю. Только та картинка, которую вы изволили дать в статье, равно как и ваши пояснения, алгоритма «сортировочной станции» никак не поясняет. Википедию лучше читайте, ей богу.

[valerar]

Ну зря Вы так.
Картинка, кстати хорошая и правильная для реализации «сходу».
За книжки спасибо.

[DoctorMoriarty]

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

[DoctorMoriarty]

Лафоре чист от ереси (цитирую добытую из недр харда его «Структуры данных и алгоритмы в Java»):
"Преобразование инфиксной записи в постфиксную (...) никакие арифметические операции в нем не выполняются. Конечной целью является не вычисление результата, а расположение операторов и операндов в новом формате постфиксной записи."
Так что автор статьи что-то не так понял. Вероятно, его смутило то, что Лафоре посвятил пару страниц сравнению того, как происходит «человеческое» вычисление выражения, записанного в традиционном для математики виде и того, как происходит преобразование в постфикс — и, кстати, Лафоре приводит это как раз для того, чтобы доказать новичку то, что ничего чуждого человеческому восприятию в постфиксе на самом деле нет.

[GlukKazan]

И это говорит о многом...

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

[valerar]

Использовать и понимать несколько разные вещи. Мы часто в жизни используем то, что до конца не понимаем. Поэтому и предложено приверженцам одного стека и простоты суммарного алгоритма преобразование — расчёт провести натурный эксперимент на бумаге. Такие эксперименты сильно прочищают мозги.

[ETCDema]

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

[valerar]

Когда в мозгах отсутствует понимание ни тесты ни профилирование не спасают, тогда только карандаш и бумага.

[picul]

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

[GlukKazan]

Я не использую то чего не понимаю. Например, я не использую БПФ. Собственно, мне и не требуется.

[valerar]

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

[Druu]

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

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

[valerar]

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

[berez]

Удалил — фигня получилась

[niklisto]

Если уже до такого преобразовали, то посчитать в чем проблема-то?

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

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

Вообще ОПН imho удобнее применять сразу при разборе выражения «A + B * (C — D / (E + F))». Тогда просто два стека нужно использовать. Один для чисел, второй для операций. Общий алгоритм немного сложнее естественно будет. Но результат тот же.

[valerar]

Хорошо. Давайте я попробую по ваше методе.
Участники: 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. непосредственно расчёт формулы. Это уже любителям рассказывать про всё за один проход.
Согласен с Вами, использовать сразу два стека сильно эффективнее (часть расчётов происходит сходу, но тогда придётся работать со скобками, а это уже больно сердцу «безскобочников».
Кстати, Вы очень замечательно заменили первичное хранилище ОПН очередью. Вы первый кто вообще произнёс это слово в обсуждении.
Не знаю как у Вас, а у меня точно складывается ощущение, что большая часть комментирующих плохо представляют работу алгоритмов на ОПН. И не понятно что с этим делать… :((

[jetexe]

Во первых входная очередь токенов — это вход (FIFO), он будет всегда вне зависимости от нотации и алгоритма, так что при расчете используется всё-таки один стек (LIFO).

работа возможно только с 2-мя выходными объектами

Но у вас же он один (стек LIFO) в котором и лежит первым элементом r5 (результат вычисления)…

у нас получается три этапа:1. преобразование в ОПН

Обсуждали не раз токенизация нужно при любом алгоритме и любой нотации, но входную строку преобразовывать в очередь (FIFO) можно «на лету» без перемещения по строке

2. перенесение операндов в стек 3. непосредственно расчёт формулы

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

часть расчётов происходит сходу, но тогда придётся работать со скобками, а это уже больно сердцу «безскобочников».

ну вы же сами вот только что… без скобок… В инфиксной записи это выражение: ((F+E)/D -C)*B+A вам ведь в ОПН не понадобились скобки.

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

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

Но вообще вы уже ближе подошли к пониманию алгоритма расчета ОПН

[valerar]

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

Во первых входная очередь токенов — это вход (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. Просто интересное наблюдение.
Однако вернёмся. При вычислениях на лету мы вынуждены ориентироваться на не до конца разобранную формулу и можем рассчитывать только однозначно определённые фрагменты. "(" не позволяет однозначно определить завершённость фрагмента, который можно было бы уже рассчитать, поэтому мы помещаем её в стек операций — она будет служить отсечкой реверса при возвращении к прямому анализу символов исходной строки. ")" — фиксирует завершённость фрагмента и позволяет произвести его расчёт. Так что здесь просто немного разные алгоритмы. Хотя, блин, у меня не выходит из головы как вы преобразовались тогда без скобок. Да и что-то последовательность операций встречная по отношению к операндам в очереди. Ладно, это потом.

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

Спасибо, конечно, за комплимент, но я, с вашего позволения, его отклоню. Где-то может язык и терминология сблизились. Я начал лучше понимать используемый вами язык. А моё видение и понимание вначале достаточно полно показано в статье. И вроде пока не изменилось с тех пор.

[niklisto]

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

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

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

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

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

[valerar]

Ну вроде как я начинаю понимать ваш язык. Радует.
С учётом преамбулы с пунктами 1.2.3. нормально. Наше видение здесь совпадает.
А вот это меня заинтересовало.

На этапе выполнения вместо переменных подставляются реальные значения и быстро, в один проход, с одним стеком, выражение вычисляется.

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

Основное применение — интерпретаторы и компиляторы.

Это снимает многие вопросы к дискуссии по этой статье. Спасибо.

[valerar]

Ну не целый день, тут Вы уж загибаете, но раз пять помню. :)

[picul]

каждый операнд участвует в процессе три раза:1. инициализация переменной 2. помещение в стек 3. извлечение из стека для операции. То есть, если отбросить сами операции, то получаем три прохода по одному операнду

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

Основное применение — интерпретаторы и компиляторы.

Это снимает многие вопросы к дискуссии по этой статье. Спасибо.

Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.

[valerar]

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

Хотелось бы поинтересоваться, в какой практической ситуации имеет смысл применять Пинг-Понг.

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

[picul]

на длинных сложных формулах, которые нельзя заранее откомпилировать

Вроде выяснили, что ОПН будет эффективнее во всех смыслах кроме понимания ( субъективно для Вас ).

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

Несложно реализовать и в ОПН, и в деревьях.

Можно приспособить к разбору иерархических смысловых групп, если они имеют соответствующее обрамление

Не очень понимаю, о чем вы, но звучит как задача, которая решается деревьями.

В образовании, особенно для школьников.

Но если в будущем он неприменим, зачем тратить время школьника?

Вы меня застали в расплох, я об этом ещё не думал.

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

[valerar]

Вроде выяснили, что ОПН будет эффективнее во всех смыслах кроме понимания ( субъективно для Вас ).

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

Несложно реализовать и в ОПН, и в деревьях.

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

Не очень понимаю, о чем вы, но звучит как задача, которая решается деревьями

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

Но если в будущем он неприменим, зачем тратить время школьника?

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

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

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

[Druu]

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

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

Вы не предполагайте, просто рассмотрите ОПН и ваш алгоритм на какой-нибудь реальной формуле и посчитайте операции.

[valerar]

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

[Druu]

> Однако готов провести такой эксперимент.

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

[zagayevskiy]

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

[Zenitchik]

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

Ну, психам и не придётся программировать. А нормальные люди от ОПН никак не страдают.

[Deosis]

Таким образом алгоритм Пинг-Понг максимально приближен к человеческому восприятию и требует минимального количества ресурсов.

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

[valerar]

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

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

[Deosis]

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

[valerar]

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

[darkdaskin]

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

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

[valerar]

А вопрос по сути — просто из интереса, а как еще можно было этот велосипед соорудить)

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

[valerar]

Я не совсем понял конечный результат расчёта.

надо рассчитать комплектующие для его изготовления.

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

[valerar]

Это и было для расчета конструкторской документации. Причем внутренней, на изготовление деталей.

Ну вот Вы и стали упорядочивать мои мозги по вашей задаче :)

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

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

[valerar]

Ну да… Я тоже про это подумал. Как-то более-менее объективно оценить насколько эта операция будет забирать на себя ресурсы у меня получилось только чисто логически. Однако, сокращение интеллектуальных операций при работе с каждым символом может скомпенсировать эти затраты. Специализировано этим вопросом не занимался, поэтому ничего внятного сказать не могу.

[evkochurov]

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

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

[valerar]

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

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

1. Если встретилось число, кладем его в стек;

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

2. Если встретилась операция, достаем с вершины стека операнды для нее, вычисляем, результат кладем в стек.

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

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

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

[Deosis]

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

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

[valerar]

Да, похоже вы правы.

Проблему со сборкой чисел можно решить на другом слое.

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

[evkochurov]

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

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

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

[valerar]

Рад что мы пришли к согласию :)

[sshmakov]

Я не понял, что в результате делает алгоритм автора — вычисляет выражение?
Потому что алгоритм, с которым он сравнивает, названный "Алгоритм для ОПН взят из Wiki" и картинка под ним, выражение как раз не вычисляет, он служит для преобразования инфиксной нотации в постфиксную.

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

[valerar]

Я не понял, что в результате делает алгоритм автора — вычисляет выражение?

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

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

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

[sshmakov]

В алгоритме ОПН это вы добавили:

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

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

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

[valerar]

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

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

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

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

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

[sshmakov]

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

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

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

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

Да, представьте себе. Потому что кроме вычисления мне нужна и информация о задействованных переменных. Например, здесь на 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)

[valerar]

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

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

Ну в первом алгоритме только оценочное суждение: «должны были остаться» — это не фиксация этапа проверки.
В представленном алгоритме так же не выделяется этап проверки парности скобок, хотя он присутствует и да, до начала разбора строки. Но так же не присутствует проверка деления на ноль, хотя такая ситуация может просто возникнуть в процессе вычисления. Но я считал важным показать сам принцип, а не обвесы вокруг. Возможно в этом я и не прав.

[Druu]

> Но речь даже не об этом. Сколько и каких сортировок нужно сделать, чтобы из инфиксной (привычной нам) записи сделать постфиксную?

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

[valerar]

Никаких сортировок делать не надо.

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

Преобразование в ОПН выполняется за единственный проход элементарно

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

[Akon32]

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

[valerar]

Ну я даже в статье привёл пример его работы, вообще-то. Я что-то неправильно отразил в его работе?

Он же элементарный. И сложность O(n).

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

[Akon32]

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

[valerar]

Ну вот мы, похоже, и договорились :)

[Druu]

> Простите, а «сортировочная станция» это тоже я придумал?

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

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

Давайте

(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**-+

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

[valerar]

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

если цифры на место подставить то вычисление в ОПН я произведу гораздо быстрее чем вы в оригинале

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

[GlukKazan]

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

[GlukKazan]

Да, так можно.

[Druu]

> 1. наличие (-1) каким образом сохранились скобки?

Потому что это отдельный токен.

> выражение «EFGHJ(-1)*-»

Это не выражение ОПН, так же как ((1+2)-3 — не выражение в инфиксной форме (хотя, оно может являться неким куском выражения). Так же как в инфиксной записи выражение характеризуется закрытием операции и сбалансированностью скобок, в ОПН выражение характеризуется тем, что в нем символов операндов ровно на 1 больше, чем символов операций.

> 3. Каким образом будет рассчитываться выражение, если оно лежит в одном стеке, а мы должны для выполнения к каждой операции присоединить ещё и пару операндов?

Вы говорите какую-то бессмыслицу. Никаких выражений в стеке при вычислении ОПН не лежит и ничего никуда не присоединяется.

[valerar]

Потому что это отдельный токен.

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

Это не выражение ОПН,

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

Я как-то и задал вопрос. поскольку мне показалось что по приведённому вами критерию конечная формула написанная вами не проходит, хотя инфиксная исходная форма корректна. Проверил ещё раз — не проходит: операндов 16 (без (-1), а операций только 13. Вопрос не в том, что Вы ошиблись — вопрос в том, что контроль постфиксной записи человеком очень затруднён, особенно на этапах начального изучения ОПН.

Вы говорите какую-то бессмыслицу. Никаких выражений в стеке при вычислении ОПН не лежит и ничего никуда не присоединяется.

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

[Druu]

> Проверил ещё раз — не проходит: операндов 16 (без (-1), а операций только 13.

Я не знаю, что вы считали, но вот в этой строке:
ABC*D/+EFGHJ(-1)*-I+/LMN-*-R-S+W**-+


17 операндов:
ABCDEFGHJ(-1)ILMNRSW

и 16 операций:
*/+*-+/-*--+**-+

и контроль этого факта проще чем контроль сбалансированности скобок в исходном выражении

> вопрос в том, что контроль постфиксной записи человеком очень затруднён

Контроль инфиксной записи затруднен еще больше, поскольку там есть скобки.

> Выражение, преобразованное вами ранее, так понимаю, лежит в одном стеке.

Никаких выражений в стеке не лежит.

> Если никаких выражений в стеке не лежит, то что там лежит, куда делось выражение, ведь у нас больше ничего нет кроме стека?

После построения выражения в постфиксной форме, там ничего не лежит.

> ведь у нас больше ничего нет кроме стека

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

[valerar]

Вот тут не соглашусь, название точно определяет суть. Поместить знак операции ЗА операндами эти нисколько не естественно. a+b как-то отличается от ab+, не говоря уже о более сложных выражениях.

И да для преобразования «обычной» записи в Естественную Польскую Запись всегда использовался алгоритм с двумя стеками.

Почитайте гуру и многих комментаторов, очень часто речь идёт об одном стеке. И это сильно сбивает, когда сталкиваешься с этим впервые.

[jetexe]

Почему вас тогда не смущают функции? Они же вообще в префикс ной написаны: doSomeShit(a,b)

[valerar]

Они меня и не смущают. Это отдельный слой, который можно рассчитывать самостоятельно. Ни на какие приоритеты они не влияют. Главное их выделить.

[lastuniverse]

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

[zugr]

Кто-то очень не умный в Обратной Польской Записи добавил слово «обратная», это и приговорило этот способ записи всегда быть «неправильным». Хотя вполне себе прямой и чёткий алгоритм в записи, что делать и с чем! И да для преобразования «обычной» записи в Естественную Польскую Запись всегда использовался алгоритм с двумя стеками.

[valerar]

Странно… Вроде я уже на этот комментарий отвечал.
В двух словах.
1. Название верное. a+b, не тоже самое что ab+. Инверсия отношений налицо.
2. Алгоритм достаточно плохо воспринимаемый, требует серьёзного натаскивания.
3. Многие, в том числе и в умных книжках, упорно говорят об одном стеке, что сильно напрягает.

[jetexe]

вычисление в один стек, преобразование в два…

[valerar]

???

[GlukKazan]

Ну нету в польской нотации скобок, просто нету (и приоритетов операций нет тоже). Мне можете поверить, я иногда программирую на Форте. Для вычислений используется один стек. А вот для преобразования из инфиксной (со скобками) записи в постфиксную удобно использовать алгоритм, использующий два стека (один для операндов, другой для операций). Последний как раз используется чтобы разрулить приоритеты и скобки инфиксной записи и положить операнды на стек в правильном порядке. Кстати, есть ещё префиксная запись. Её тоже будете критиковать?

[valerar]

Можно я просто ссылкой отделаюсь
habrahabr.ru/post/351782/?reply_to=10720704#comment_10720704

[GlukKazan]

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

[valerar]

Да конечно. Можно просто сказать что есть одна входная корзинка и две на выходе. А как корзинки называются — дело третье.
И ещё, я критикую не саму ОПН, а её безальтернативность в процессе обучения.

[GlukKazan]

Прежде всего, есть два совершенно разных алгоритма:

1. Преобразование из инфиксной записи в постфиксную
2. Вычисление значения выражения в постфиксной записи

Которые вы почему-то не различаете (поскольку в вашей задаче разбор выражения подразумевает его вычисление) и изобретаете третий алгоритм:

3. Вычисление значения выражения в инфиксной записи

Что называется, да ради бога. Теперь можно оценить сложность (1+2) и (3). Это можно сделать математически или экспериментально. Как минимум, очевидно, что (3), в отличии от (1) не однопроходный. Чего я не понимаю, так это почему вы называете всё это критикой ОПН? ОПН — это нотация (у аббревиатуры Н на конце). Критиковать нотацию приблизительно также бессмысленно, как облака на небе. Она просто есть (как и задача перевода в неё). Можно критиковать учебный процесс, чрезмерно акцентирующийся на алгоритме (1), но на мой взгляд это немножко натянуто. Это действительно хороший алгоритм, почему бы его не преподавать? В конце концов, вы не предложили своего варианта решения задачи, для которой предназначен (1) и не показали, что (3) вычислительно проще чем (1+2).

[valerar]

Прежде всего, есть два совершенно разных алгоритма:

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

почему вы называете всё это критикой ОПН?

Потому что в основе лежит именно запись (представление), в которую переформатируют инфиксную (привычную) запись, чтобы уже потом получить конечный результат. И тогда встаёт вопрос: «А надо ли корёжить исходное?» И при этом тратить учебное время на слом мозгов молодёжи. Для себя я ответил:«Не надо ни первое, ни второе.» Если ОПН была сделана во времена ограниченности инструментов управления кодом и железом, то при наличие на сегодня адекватных инструментов можно пожалеть молодёжь и не вбивать им в мозги старые дрожжи. Здесь рассматривались два ПОДХОДА к решению одной задачи.
Надеюсь я объяснил почему именно критика ОПН, а не конкретных алгоритмов и аппаратных ускорителей (акселераторов).

[GlukKazan]

Нас учили, что там два чёрных ящика, связанные в «конвейер». А «корёжить» исходное иногда надо, особенно если занимаешься разработкой компиляторов, а не от нечего делать изобретаешь сферичный алгоритм вычисления значения выражений. Я ведь не зря ссылку на «Dragon Book» дал. Если вы занимаетесь этим вопросом профессионально, эта книга должна быть прочитана. В противном случае, конечно, можно изобретать всё что угодно, но не удивляйтесь тому, что ваших благих побуждений не понимают те, кто занимается вопросом более глубоко.

[valerar]

Ну за ссылку я уже поблагодарил.

Нас учили, что там два чёрных ящика, связанные в «конвейер».

Хм-м… давайте обратимся к классикам.


Где бы вы поставили на этой картинке разграничение между двумя чёрными ящиками? Действительно интересно. Я, например вижу единый процесс в котором присутствует и считывание и сортировка и вычисления вперемешку.

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

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

[GlukKazan]

Я уже несколько раз говорил и повторю: Вы придаёте этому вопросу слишком большое значение. ОПН, как вы её называете, крайне удобна, например, при разработке компиляторов, но вера… Слишком много чести. Что касается картинки — для меня это не классика. Если таким образом (на примере вычисления выражения) объясняется алгоритм "сортировочной станции", согласен с вами — вреда от такого объяснения больше чем пользы. В печь такую книгу.

[valerar]

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

[GlukKazan]

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

с Вами у нас очень как-то по смешному

Ага. Такое впечатление, что вы живёте в другом измерении. Тех простых вещей, которые вам талдычат не понимаете, да и сами говорите что-то не до конца понятное. Вот это например:

Но тогда «безскобочники» встают на уши. Не начинают разбираться, а сразу бросаются в бой.

Смешно получается. О чём вы вообще?

[valerar]

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

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

Ага. Такое впечатление, что вы живёте в другом измерении.

Так и есть. Аналитики и программисты — это жители разных планет. Мышление разное, понятия разные, языки разные. Только какое-то время совместной работы в группе позволяет выработать общий язык.

Тех простых вещей, которые вам талдычат не понимаете, да и сами говорите что-то не до конца понятное.

Во-во и я про то же. Нормально. С кем-то научимся друг друга понимать, кто-то перестанет обращать внимание. Нормальный процесс.

Смешно получается. О чём вы вообще?

Не, не хочу сейчас про технику. Нафига такой хороший диалог портить. Будет интересно, объясню в следующем комментарии.

[Deosis]

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

А потом у вас будет лагать блокнот, потому что "молодежь" не догадывается об ограничениях железа.

[netch80]

> Кто-то очень не умный в Обратной Польской Записи добавил слово «обратная», это и приговорило этот способ записи всегда быть «неправильным».

«Добавил» потому, что «прямая польская» запись это префиксная, как в LISP. И идут эти термины «прямая» и «обратная» от работ Яна Лукасевича в 1920-е годы. Слово «польская» добавили уже после него, но в его честь. И это были очень умные люди, которые основали нынешнюю Computer Science.

И ничего «неправильного» в этом нет, кроме того, что такую запись, в отличие от префиксной, сложнее парсить и модифицировать — надо рассчитывать просмотром назад, где части выражения.

> Естественную Польскую Запись

Своими нововведениями вы нарушаете устоявшуюся терминологию. Не думаю, что это будет принято обществом.

[jetexe]

Толи автор перепутал алгоритмы вычисления/разбора ОПН, толи статья касается преобразования вариантов записей… Откуда-то взялись скобки в ОПН… я запутался.
В конце сравнения двух (вообще трёх) алгоритмов:

• Первый (первые два) сначала преобразуют строку инфиксной нотации в постфиксную (первый алгоритм) потом её расчитывает(второй алгоритм).
• Второй (третий) расчитывает строку

Почему при этом строится вывод о вреде ОПН?

[valerar]

Автор рассматривал целостные алгоритмы от получения входной строки до получения конечного результата. Сортировка в ОПН бессмыслена без расчёта результата ради которой она делалась.

[jetexe]

Какая сортировка? В ОПН нет приоритетов, нечего сортировать. Там нет скобок.
(1+2)*(3+4) — инфиксная (привычная вам)
1 2 + 3 4 + * — ОПН
1. Вход 1, стек {}, пушим в стек
2. Вход 2, стек {1}, пушим в стек
3. Вход +, стек {2,1} Берем из стека два элемента проводим операцию, возвращаем в стек.
4. Вход 3, стек {3}, пушим в стек.
5. Вход 4, стек {3,3} пушим в стек.
6. Вход +, стек {4,3,3} Берем из стека два элемента проводим операцию, возвращаем в стек.
7. Вход *, стек {7,3} Берем из стека два элемента проводим операцию, возвращаем в стек.
7. Вход пусто, Стек {21}. Конец. В стеке решение

[valerar]

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

Ну и так далее…
Как видим всё не так просто.

[AnutaU]

Разделить строку на токены («поставить разделители» по-вашему) можно сделать в том же проходе по строке, что и преобразование в ОПН.

[valerar]

В одном проходе и то и другое? — Поделитесь.

[GlukKazan]

Вот тут. Правда не про «ОПН», но сам подход с раздельными лексером и парсером вполне работает (за один проход по исходному тексту, да).

[GlukKazan]

А если потом будет точка(разделитель разрядов)?

А вот чтобы не заморачиваться с точками, надо исходный текст предварительно разбивать на лексемы.

[valerar]

Ключевое слово «предварительно».

[GlukKazan]

Пытаетесь поймать меня на слове? Похвально. Ещё раз повторюсь, это «предварительно» вполне можно сделать в том же (и единственном) проходе. Без возвратов по тексту. Доступно?

[jetexe]

1. Ничего не делаем. Вы опять нотации перепутали.
2. Да сохранить. причем можно в тот же стек. Можно в регистр. Вообще это всё происходит "на лету" без операций над всей строкой. Вы же в пин-понге тоже должны как-то понимать где число закончилось, где разряды, etc.

[valerar]

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

[jetexe]

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

[valerar]

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

[valerar]

Не вижу смысла. Мы обсуждаем алгоритмы.

[valerar]

Просто я проверял работоспособность алгоритма на java и использовал некоторые термины связанные с ней. На java алгоритм работает нормально.

[picul]

Итак, все ясно — автор очевидно просто не смог реализовать свой же алгоритм. Зачем иначе скрывать реализацию?

[valerar]

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

[picul]

Если Вас не связывает NDA или что-то в этом роде, то выложить имеющуюся реализацию алгоритма в Интернет может помешать либо отсутствие Интернета, либо отсутствие реализации.

[valerar]

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

[picul]

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

[valerar]

Ну не надо так уж совсем. на Хабре большая часть статей на реализованность такой методологии не тянет. Да и не задача статьи представить техническую документацию или полноценное исследование.
Задача статьи познакомить с артефактом, заставить подумать, а вовсе не дать исчерпывающие характеристики ситуации, объекта, артефакта. множество статей просто знакомят с опытом автора, его мнением в той или иной сфере.
Задача этой статьи была чётко обозначена: не терроризируйте мозги студентов ОПН, потратьте учебное время на более полезные вещи. Как возможность хоть какой-то альтернативы был представлен Пинг-Понг. Я постарался его представить как можно подробнее, чтобы его реализация не представляла никакого труда на уровне школьника. Насколько получилось, настолько получилось. Основные дебаты шли вокруг ОПН и это нормально. Статья свою задачу выполнила.
Если вас конкретно интересует что-то в алгоритме или его реализации спрашивайте, даже конкретный кусок кода постараюсь отскринить, но на личную почту — чистить код не буду (он даже на мой дилетантский взгляд требует чистки) мучиться снова со вставкой картинок на Хабре не готов, к дискуссиям «так не делают» — тоже.
как-то так.

[Zenitchik]

Вот потому хабр и стало тошно читать, что авторы так думают.
Пусть статей будет в 10 раз меньше, но пусть они будут нормальными.

[valerar]

Зря Вы так. Статьи нужны разные. Нельзя всегда читать техдокументацию.

[Zenitchik]

Для лирики есть ЖЖ.

А статья на Хабре, ИМХО, должна быть похожа на научную статью.
Люди же гуглить будут. И вместо достойной статьи в выдаче попадётся «опыт автора и его мнение». Некомпетентное, прошу заметить. Зачем так гадить людям?

[valerar]

ЖЖ для трёпа и для вбросов.
Хочу напомнить Вам такую фамилию как Циолковский. Попробуйте посмотреть не только его космические расчёты. Кстати, история публикации его работ достаточно интересна. Обратите внимание что я не употребил слово «научных».

[Zenitchik]

ЖЖ для трёпа и для вбросов.

Пардон, а Вы что написали?

Циолковского — читал. Всего или почти всего. Честно говоря, в основном — не оценил. Впрочем, в те времена все писали так же мутно.

[valerar]

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

[impetus]

Я тоже читал и оценил — «майн кампф» отдыхает. вообще то, что он ещё не запрещён повсюду как экстремист/расист какой-нибудь — чисто чья-то недоработка потому что неуловимый Джо, но рано или поздно его довыпячивают и кто-то озабоченный таки прочтёт, и найдётся прокурор, до звёзд охочий…

[picul]

Циолковский был первым в своем деле, а Вы пришли в подробно изученную область и предложили перечеркнуть работу признанных ученых и вместо нее использовать самый примитивный подход, который можно представить. Так что Ваши высказывания сравнимы не с работами Циолковского, а с предложением Илону Маску забросить этот его SpaceX и вместо этого начать писать статьи в стиле Цилковского.

[valerar]

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

[picul]

Я нигде не предлагал перечеркнуть, нигде не предлагал «вместо».

Читали предпоследнее предложение своей статьи? На всякий случай продублирую: «Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» И это после того, как вы предложили алгоритм, эффективность которого можете аргументировать только в «сфере обучения», и то лишь своим субъективным мнением.

Напрягло не просто так, а потому, что перед этим я поразбирался с ОПН.

И, как видно из комментариев, до сих пор с ней не разобрались. То есть всем ВУЗам мира нужно немедленно включить в свою программу алгоритм, придуманный человеком, который ниасилил ОПН?

Надо ли его вдавливать в молодые мозги?

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

И на нём десятки статей С ОПН и ни одной реальной альтернативы (рекурсию и деревья не считаем).

У любого понятия нет альтернатив, если не считать его альтернатив.

[valerar]

Читали предпоследнее предложение своей статьи? На всякий случай продублирую: «Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» И это после того, как вы предложили алгоритм, эффективность которого можете аргументировать только в «сфере обучения», и то лишь своим субъективным мнением.

Мнение я и не изменил. А вот фраза, о которой Вы почему-то не упомянули: «Таких интуитивно понятных алгоритмов, думаю, достаточно много.» И, знаете ли, я действительно думаю, что ни один я «такой умный». А П-П лишь повод подсветить проблему. Так что про «немедленно включить в программу» — это Вы уже сами придумали, ну или дайте ссылку, чтобы освежить мне память.

Никто никуда ОПН не вдавливает

Обсуждение говорит об обратном. Хорошее осуждение, даёт много материала для анализа.

[picul]

Мнение я и не изменил.

про «немедленно включить в программу» — это Вы уже сами придумали

«Так почему же студентов до сих пор мучают всякой хренью, придуманой в незапамятные времена?» — это не призыв? Или Вы, как любой уважающий себя диванный эксперт, только недовольство выражаете, а прямых предложений сделать не способны?

Обсуждение говорит об обратном.

Обсуждение говорит о том, что ее сложно вдавить лично Вам.

[valerar]

Ах да, могу ещё прислать журнал прогона. где замечательно видны все этапы работы алгоритма вместе с формированием фрагментов, операндов и получением результатов.

[GlukKazan]

А вы не думали о том, что разбор выражения не всегда производится для его вычисления? Например можно разобрать выражение в дерево, продифференцировать его, упростить, а потом снова сериализовать в выражение. Можно и вычислить заодно, конечно.

[valerar]

Не в данном случае.

[GlukKazan]

Дело ваше.

[Druu]

> Автор рассматривал целостные алгоритмы от получения входной строки до получения конечного результата.

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

[valerar]

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

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

Ну как же ОПН нет? А в какой нотации тогда строится постфиксная запись?

[Druu]

> Ну как же ОПН нет? А в какой нотации тогда строится постфиксная запись?

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

Что именно вы доказать-то пытались, можете четко сформулировать? Тезисно.

[valerar]

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

[Druu]

> Поэтому я говорю о комплексном алгоритме с использованием ОПН.

Где в нем используется ОПН? Пальцем покажите.

[valerar]

Так понимаю, всё это время мы разговаривали про разное…
Бывает.

[Druu]

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

[valerar]

Читайте комментарии, статью и всё вам будет.

[Druu]

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

[valerar]

Хотели рассмешить? — получилось. Я уже посмеялся. Мне достаточно.

[Druu]

Не надо смеяться, просто ответьте, пожалуйста, на вопрос. Что в этом сложного?

[berez]

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

[valerar]

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

[GlukKazan]

Вы боретесь с ветряными мельницами. Нет никакого «засилия ОПН».

[picul]

Ну и как-то это было скорее против засилия ОПН в учебном процессе.

Насколько я понял, алгоритм, предложенный в статье является формализацией подхода, который используется человеком. Зачем же рассказывать студентам то, что они умеют и практикуют со школьных времен? Не лучше ли рассказать про ОПН, которая выигрывает у Пинг-Понга в производительности и используется в реальных проектах?
Вот представьте, что лектору нужно рассказать, как найти подстроку в строке. Можно предложить алгоритм перебором за O(N^2), до которого любой студент и сам додумается, а можно рассказать о чем то вроде алгоритма Кнута-Морриса-Пратта, который не стыдно использовать в продакшене. Что по Вашему полезнее/интереснее? Лично мне второе, говорю Вам как студент))

[valerar]

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

Да.

Зачем же рассказывать студентам то, что они умеют и практикуют со школьных времен?

Чтобы понимали наличие альтернатив и разных подходов. Плохо когда все дуют в одну дуду. ограничивает возможности развития.

Не лучше ли рассказать про ОПН, которая выигрывает у Пинг-Понга в производительности и используется в реальных проектах?

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

Что по Вашему полезнее/интереснее?

Что интереснее это индивидуально. А вот полезнее знать где и что применить, причём независимо от текущей моды или коронки «так принято».

говорю Вам как студент))

Эх, хорошее время… Кстати, и время поиска нового, а не только заучивания устоявшихся норм и правил.

[picul]

задачи разные и преимущество в одних может оказаться недостатком в других

ИМХО единственное достоинство Пинг-Понга — это его простота ( при чем только в понимании, в реализации не все так просто ). И я не считаю, что простота должна быть главным аргументом для выбора алгоритма.

Во-первых, что выигрывает это ещё вопрос. Посимвольный разбор с разветвлённой логикой достаточно затратен сам по себе.

Редкие случаи посимвольного разбора в ОПН в Пинг-Понге заменяются на тест регулярными выражениями по любому поводу. Количество проходов по исходной строке может быть очень большим — и это против одного прохода в ОПН. Пункт 'Замена фрагмента "(...)"' тянет за собой столько же копирований памяти. У меня нет реальных цифр, но я думаю, что Пинг-Понг немало проиграет ОПН в производительности.

Кстати, и время поиска нового, а не только заучивания устоявшихся норм и правил.

причём независимо от текущей моды или коронки «так принято».

Никто ничего не заучивает — все просто пользуются самым эффективным решением.

[valerar]

ИМХО единственное достоинство Пинг-Понга — это его простота ( при чем только в понимании, в реализации не все так просто )

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

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

Удивили. Алгоритм на ОПН — это ВСЕГДА посимвольный разбор. Да и

Пункт 'Замена фрагмента "(...)"' тянет за собой столько же копирований памяти.

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

Никто ничего не заучивает — все просто пользуются самым эффективным решением.

Когда говорят «самое эффективное» всегда хочется поинтересоваться: «С чем и как сравнивали?». И это я не про обсуждаемые алгоритмы.

[picul]

Предлагаю оставить вопрос эффективности в покое. Мне достаточно что алгоритм прост и понятен.

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

Вряд ли мы оба сейчас готовы квалифицированно ответить на такое однозначно.

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

Удивили. Алгоритм на ОПН — это ВСЕГДА посимвольный разбор.

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

лучше стоит восстановить информацию по замене фрагментов в строке.

Не совсем понял, что имелось в виду. Если я правильно понимаю таблицу с описанием алгоритма, после каждого теста по regex'пу выполняется замена обрабатываемого фрагмента строки на результат, что ведет к копированию всего хвоста строки. Если конечно длина результата не совпала с длиной фрагмента, что маловероятно.

Когда говорят «самое эффективное» всегда хочется поинтересоваться: «С чем и как сравнивали?».

Серьезным подходом считается написать реализации обоих подходов и сравнить. И при разработке новых алгоритмов всегда стоит сравнивать их с существующими аналогами.

[valerar]

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

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

в данном случае оно окупится еще на этапе разработки, так как на реализацию Пинг-Понга уйдет намного больше времени, чем на ОПН ( ИМХО ).

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

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

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

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

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

Не совсем понял, что имелось в виду.

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

Если я правильно понимаю таблицу с описанием алгоритма, после каждого теста по regex'пу выполняется замена обрабатываемого фрагмента строки на результат, что ведет к копированию всего хвоста строки. Если конечно длина результата не совпала с длиной фрагмента, что маловероятно.

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

Серьезным подходом считается написать реализации обоих подходов и сравнить. И при разработке новых алгоритмов всегда стоит сравнивать их с существующими аналогами.

Кто бы спорил с такой очевидной вещью если бы не такое понятие как трудозатраты.
Ладно на вопросы ответил, возвращаемся к логическому сравнению алгоритмов.
Начнём с того что отбрасываем как присутствующее в обоих алгоритмах — это элементарные операции + — * /, несмотря на то, что операция / тяжелее операции + как минимум в 40 раз. Они присутствуют одинаково в исходной формуле.
Что нам надо сделать для КАЖДОГО символа в ОПН:
Сортировка и расчёты
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с образцами (цифры, знаки операций, скобки -16 образцов). Пусть образцы лежать в некой оптимизированной хэш таблице, но каждый нужно выдернуть и сравнить с поступившим символом, т.е. занести в регистр и произвести операцию сравнения. По совпадению перейти на команду соответствующей ветки. И тут 50 на 50 угадал ли процессор со следующей командой, уровень неопределённости достаточно высок. то бишь с конвейером могут быть проблемы и нехилый шанс заработать штраф в виде пропущенных тактов.
3. Для любой из веток проверить предусловие.
3.1 для цифры (работаем с вещественными числами с длиной >1) поместить в буфер для сборки числа. Мы не знаем следующего символа и не в курсе сформировано у нас число или нет.
3.2 для скобки открывающей. Увеличить счётчик скобок на 1; поместить в стек операций.
3.3 для скобки закрывающей. Взвести флаг «расчёт фрагмента»; проверить буфер сборки числа и если он не пуст, хотя он в данном случае всегда не пуст — проверку можно пропустить, перенести число в стек операндов; перейти на ветку расчёта фрагмента, реверс до открывающей скобки (расчёт фрагмента будет ниже); уменьшить счётчик скобок на 1, хотя это можно сделать по достижению скобки открывающей.
3.4 для операции. вытащить из стека предыдущую операцию и передать в регистр АЛУ для сравнения приоритетов.
3.4.1 если приоритет предыдущей операции ниже или это "(" или стек пуст, записать данную операцию в стек.
3.4.2 если приоритет предыдущей операции такой же, то записать текущую в промежуточное хранилище; вытащить предыдущую операцию из стека операций; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; вытащить текущую операцию из промежуточного хранилища и положить в стек операций.
3.4.3 если следующий оператор "(". передать текущую операцию в АЛУ; вытащить 2-й операнд из стека; вытащить 1-й операнд из стека; результат положить в стек; удалить "(" из стека; уменьшить счётчик скобок на 1( вверху был вариант когда счётчик уменьшался по ")" — это не особо важно); перейти на адрес последнего проверенного символа (его перед этим тоже сохранить где-то надо, а теперь считать) и ветку последовательного перебора.
Уфф! не уверен, что ничего не потерял, но вроде всё. Учтём что это для КАЖДОГО символа. Ну и обещаное.
Расчёт фрагмента от ")" выглядит теперь совсем простенько
1. Получили ")". Переходим в режим реверса. Записали адрес для последующего возврата на последовательный прямой перебор.
2. вытаскиваем предыдущую операцию. определяем что это за операция; вытаскиваем операнды (по одному), результат в стек операндов. И так в цикле до "("
3. получили "(". Закрываем расчёт фрагмента: удаляем "(" из стека; уменьшаем счётчик скобок; вытаскиваем адрес отработанной ")"; переходим на ветку прямого перебора с адреса + 1.

переходим на Пинг-Понг
1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. сравнить с ")". Если «да», то записать индекс конца фрагмента. Иначе перейти на следующий символ.
3. Зафиксирован индекс конца фрагмента в переменной. Переход на реверс; смена шаблона поиска на "(".
4. сравнить символ по направлению движения с "(". Если «да», то записать в переменную индекс начала фрагмента.
5. записать фрагмент по индексам в строку «фрагмент»; перейти на ветку расчёта умножения.
6. расчёт слоя умножения в строке «фрагмент»
6.1 поиск "*" от начала фрагмента. Если найден, то выделить операнд слева (регулярное выражение); занести в переменную начало подфрагмента; перевести в dubl; выделить операнд справа (регулярное выражение); занести в переменную конец подфрагмента; перевести в dubl; результат заменяет подфрагмент в строке «фрагмент»; продолжить поиск с начала обработанного подфрагмента. Иначе переход на блок деления.
7. блок деления — аналогично блоку умножения
8. блок сложения вычитания — аналогично предыдущим.
9. результат расчёта фрагмента записать в рабочую строку вместо фрагмента по индексам.
10 перейти к поиску следующего фрагмента

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

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

[AnutaU]

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

Здесь сложнее определить элементарные операции, поскольку неизвестны внутрянка и SnringBuilder регулярных выражений

А надо бы понимать, как это всё работает, потому что вопреки вашим предположениям на временную сложность алгоритма это повлияет.

Так что, если вы конечно не тролль, то лучше сначала разберитесь.

[nsinreal]

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

Нууу нет. Другое дело, что человек не бенчи гоняет, а слова туда-сюда.

В целом я бы сказал, что в этой задачи есть естественный предел на входящее выражение. Сомнительно, что будут гонять выражения с миллионами операндов. А значит влияние константы становится очень важным.
Этот как использование bubble sort для малых отрезков внутри quick sort — асимптотика хуже, но константа меньше сильно.

[AnutaU]

Подождите, дайте товарищу просто с биг-о разобраться, ещё успеет влияние большой константы на маленьких входных данных осознать.

[AnutaU]

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

Если это лаба для студентов, то может и не будут (хотя надо бы, конечно). Но я лично видела файлы с кодом на языке C, где встречались строки длиной по миллиону символов. Естественно, не руками написано, получилось после препроцессора. Арифметическое выражение, кстати. И это вполне рабочий код из реального проекта, компиляторы и инструменты обязаны с таким работать.

[chersanya]

несмотря на то, что операция / тяжелее операции + как минимум в 40 раз

Это-то вообще откуда? Из вычисления вручную столбиком, чтоли?

[netch80]

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

[chersanya]

О, спасибо за информацию, как-то я надеялся, что уже все 4 базовые операции (fp) почти до одной скорости в процессорах дооптимизировали — оказалось, нет :)
В gpu как я понимаю ситуация получше — беглое гугление говорит, что буквально раза в 4 отличается макс скорости + и /.

[netch80]

Хм. Тут, например, говорят про 20 раз. Отношение меньше, наверно, как раз в CPU; сложение плавучих вряд ли можно сделать быстрее 4 тактов (полная латентность), а деление получается от 20 (варианты Goldschmidtʼа). Для GPU деление обычно существенно не оптимизируют. Но, может, я тут отстал от реалий последних лет.

[valerar]

Собственно это общеизвестно. Но можете посмотреть какие-нибудь материалы по профилированию.

[Deosis]

1. достать символ из строки по адресу (чтение из памяти, запись в регистр АЛУ, подготовка следующего адреса I++)
2. результат расчёта фрагмента записать в рабочую строку вместо фрагмента по индексам.

По вашему эти операции требуют одинакового времени выполнения?

[valerar]

Нет. Вторая, конечно же, существенно тяжелее.
Вопрос только сколько потребуется маленьких в одном месте и сколько больших в другом.

[netch80]

Если взять вместо мотаний взад-вперёд по строке последовательное движение с рекурсией, которая всё равно неизбежна в случае выражений типа ((a+b)*(c-d))*e (ваш алгоритм будет вынужден считать скобки, чтобы определить пару первой скобке...) — получится самый типовой нисходящий ручной парсер типа того, что в книге Страуструпа по C++. А если добавить разбор по приоритетам операций — получится парсер Пратта. И, заметьте, никаких мотаний.

Поэтому я бы сказал, что вопрос надо заменить на другой — «если так просто писать ручные парсеры, зачем нас мучают всеми этими LL и LALR?» И вот на него уже сложно ответить методологически корректно, потому что тут как раз тот случай, когда преждевременная математизация убивает понимание.

[valerar]

Если взять вместо мотаний взад-вперёд по строке последовательное движение с рекурсией, которая всё равно неизбежна в случае выражений типа ((a+b)*(c-d))*e

Нет в алгоритме рекурсии. Есть только прямое и реверсное (обратное) движение.

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

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

получится самый типовой нисходящий ручной парсер типа того, что в книге Страуструпа по C++.

За наводку на книгу — спасибо. Обязательно посмотрю.

А если добавить разбор по приоритетам операций — получится парсер Пратта.

Здесь нет разбора по приоритетам операций от слова «совсем». Приоритетность реализуется последовательностью блоков расчёта. То есть расчёты проводятся послойно, что повышает эффективность работы конвейера.

И, заметьте, никаких мотаний.

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

[jetexe]

Предостережение потомкам: нет смысла спорить с автором, он не владеет теорией. Нервные клетки дороже.

[masai]

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

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

Более того, инфиксная форма — не единственная, которую мы используем в жизни.

Возьмём выражение (1 + 2) * 3. Это инфиксная запись. И давайте вспомним, как во втором или третьем классе мы выполняли задание «прочесть выражение»: «произведение суммы 1 и 2 и 3». Записав в виде значков получаем * + 1 2 3. А что это, как не префиксная форма? А фраза «возьми первые два числа и сложи» разве не постфиксная форма?

Да даже в быту. «Мы поможем ему» — инфиксная форма. «Мы ему поможем» — постфиксная. Всё интуитивно, мозг не взрывается от того, что действие в конце.

Мы используем инфиксную форму, как мне кажется лишь потому, что так исторически сложилось.

[jetexe]

И при этом считает его медленнее чем регулярки с копированием строки в памяти

[valerar]

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

[jetexe]

Ваша проблема в том, что вы много «считаете» вместо того, чтобы реально сесть и посчитать

[valerar]

Нет, это не моя проблема. Если кому-то будет интересно, то он это сделает. Мне нужно было решить локальную проблему — я её решил. Чтобы, если у кого-то появится потребность в подобном решении, у него была заготовка, я начал готовить статью. В процессе подготовки вылезли проблемы с данным вопросом в нашем образовании — была построена схема оппозиции. Статья свою задачу решила. Проблема даже больше, чем мне виделось исходно. Сейчас отвечу на внятные комментарии и положу проект на полку.
Как-то так.

[jetexe]

Вы знаете что такое «сложность алгоритма» и как она вычисляется? Вы пробовали её вычислить для пинг-понга?

[valerar]

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

[valerar]

Пардон, нечаянно слетел на производительность. Не умышленно.

[GlukKazan]

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

[valerar]

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

[Druu]

> При появлении скобок и вещественных операндов с длиной > 1 его эффективность сильно падает.

Каким образом она падает, если алгоритм линейный?

[valerar]

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

[Druu]

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

Любой символ все равно будет выведен из стека ровно раз. Из-за скобок эти символы просто будут выведены раньше. Количество самих выводов из-за скобок никак не меняется, только время вывода. Один символ же обработан всегда лишь однажды. Один раз кладется на стек и один раз из стека уходит. То есть сколько скобок не добавляй, это вообще не влияет на ход алгоритма. 1+2+3+4+5 вычисляется ровно так же, как (((1 + 2) + 3) + 4) + 5)

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

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

[valerar]

Я правильно понял, что единственный недостаток, вменяемый обратной польской нотации, — это неинтуитивность?

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

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

Да, я тоже видел. И они, кстати, за редким исключением, предпочитают говорить о конкретике.
Так что я не против ОПН как таковой, я против её роли в современном учебном процессе и превращения её в объект религиозного поклонения.

[valerar]

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

[GlukKazan]

Вы уже немного утомили со своей кнопкой. Покажите мне любые два коментария к этому посту в духе:

«ОПН: нажми на кнопку — получишь результат»

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

[valerar]

Ну я даже пролистал коменты. Нашёл. Однако не считаю правильным их выкладывать, поскольку они касаются третьих лиц.
А вот на свои истерики я бы посмотрел.

[ETCDema]

Краткое содержание статьи и каментов автора: "крокодил эффективнее отвертки потому что окно и все несогласные адепты ктулху".

Если много раз и из разных источников слышите фразу "разберитесь сначала", то наверно это не просто так.

Но банально разберитесь все-таки сначала, что есть что и из чего состоит "вычисление выражения, представленного строкой с инфиксной записью".

А вообще, когда начинают приплетать чувства, религию и прочие абстракции, то явно впаривают какую-то дичь.

Обратите внимание на моменты, которые являются однозначными индикаторами понимания, что тут что-то не так:

1. Движение в двух направлениях — либо нужно всю строку держать в памяти либо делать хитрую буферизацию.
2. Минимум 4 разнонаправленных прохода по одним и тем же местам строки с произвольной дистанцией:
   
   1. Найти скобку ->
   2. Найти другую скобку <-
   3. Найти оператор ->
   4. Найти операнд слева <-
3. Модификация строки: предлагается заменять фрагмент (операции копирования, выделение памяти и прочие радости), плюс для этого нужно число сконвертировать в строку и потом опять парсить
4. Подмена понятий: использование регулярного выражения это не избавление от посимвольного прохода, это использование чего-то готового.

И коллеги должны поверить, что это эффективнее однонаправленного прохода + использование стэка с числами (сортировочная станция + дерево расчета)?

[valerar]

А вот это уже серьёзный разговор, буду отвечать серьёзно.

Если много раз и из разных источников слышите фразу «разберитесь сначала», то наверно это не просто так.

Ситуация в истории не новая. Поэтому, в любом случае самопроверки и проверки утверждений комментаторов присутствуют. Ещё спасают вменяемые комментаторы.

Обратите внимание на моменты, которые являются однозначными индикаторами понимания, что тут что-то не так:

За последующий разбор отдельное спасибо.

Движение в двух направлениях — либо нужно всю строку держать в памяти либо делать хитрую буферизацию.

Это так. Однако хотелось бы пример где это не так. Формула должна лежать в памяти либо быть разбита на логические блоки.

Минимум 4 разнонаправленных прохода по одним и тем же местам строки с произвольной дистанцией:

Хотелось бы понять что Вас смущает. Тоже самое происходит в алгоритмах с ОПН. Или положить в стек -> вытащить из стека это не вперёд — назад? Или положить "(" в стек -> дойти до ")" -> развернуться и выбрать всё до "(" это не вперёд-назад? Или сначала посимвольно сформировать операнды -> положить операнд в стек -> вытащить операнд из стека Это не вперёд назад? Или в ОПН не считается? И это ещё я кратенько по ОПН.

Модификация строки: предлагается заменять фрагмент (операции копирования, выделение памяти и прочие радости), плюс для этого нужно число сконвертировать в строку и потом опять парсить

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

Подмена понятий: использование регулярного выражения это не избавление от посимвольного прохода, это использование чего-то готового.

Ну если Вы в курсе регулярных выражений, то скажите чего. Я бы, например, использовал конструкцию практически типа маски и быстро и эффективно. Что применяется при анализе КАЖДОГО символа в ОПН, чтобы определить кто есть кто, это я про символы? или у вас машина каким то неведомым способом узнаёт что это есть операция, а это число, а тут ещё и скобка затерялась. Разочарую всё через сравнение двух символов происходит. А в регулярных выражениях можно было бы попробовать механизмы поиска фрагмента текста. Очень даже эффективная технология.
Ну а по поводу использования чего-то готового, так в любом языке высокого уровня любой оператор это конструкция из блоков более низкоуровневого языка. Предлагаете писать в машинных кодах?

И коллеги должны поверить, что это эффективнее однонаправленного прохода + использование стэка с числами (сортировочная станция + дерево расчета)?

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

эффективнее однонаправленного прохода + использование стэка с числами (сортировочная станция + дерево расчета)?

про однонаправленный проход — если по рабочей строке вы идёте один раз в одну сторону, то стоит посчитать количество суеты, которая образуется в других местах.
про использование одного стека — хотел бы увидеть хоть одного человека, который сможет прийти от исходной инфиксной записи к конечному результату с помощью ОДНОГО стека на достаточно сложной формуле с вещественными операндами длиной >= 3.
Кстати, в силу вышесказанного, мне не кажется что Вы хорошо разбираетесь в ОПН.

[ETCDema]

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

[valerar]

Обратите внимание на то, что ОПН в своем сообщении я ни разу не упомянул.

Шаблон сработал. Ну извините, если это доставило вам неприятность.

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

Вы уверены что говорите именно с математической точки зрения?
А про какую эффективность вы сейчас говорите? Я, например, сразу говорил об эффективности восприятия, соответственно про эффективность быстрого применения. А Вы про какую?

[ETCDema]

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

Ни о каком насилии над личностью там нет, просто алгоритм (по сути "сортировочная станция" + вычисление с использованием стэка) хорошо демонстрирует приемы работы со стэком.

Позволю себе процитировать начало этого раздела (стр. 152):

Разбор арифметических выражений
Итак, в этой главе были описаны три разные структуры данных. Давайте немного сменим тему и рассмотрим важное практическое применение одной из этих структур.

И далее стр. 154:

На нескольких ближайших страницах подробно рассматривается процесс преобразования выражений из инфиксной записи в постфиксную. Алгоритм не из простых, так что не огорчайтесь, если что-то покажется непонятным. Если вы чувствуете, что начинаете вязнуть в теории, переходите к разделу «Вычисление постфиксных выражений». Чтобы понять, как создаются постфиксные выражения, полезно рассмотреть процесс вычисления их результата — например, вычисления значения 14 для выражения 234 + ×, постфиксного эквивалента 2 × (3 + 4).

Автор книги мог с тем же успехом иллюстрировать работу стэка на примере построения дерева выражения, но тогда пришлось бы картинок порисовать побольше.

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

Спор же (на over 200+ каментов) идет вокруг реализации этих алгоритмов и эффективность реализации П-П против "сортировочной станции" + вычисление с использованием стэка вызывает абсолютно обоснованные сомнения. (В топике о реализации говорит как минимум отсылка к использованию Regex)

И еще одна цитата из книги (опять же стр. 152):

Материал данного раздела в каком-то смысле можно рассматривать как «до-
полнительное чтение». Он не обязателен для понимания книги, а в вашей повсе-
дневной работе вам вряд ли придется часто писать код разбора арифметических
выражений

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

Думаю дальнейшая переписка по этой теме бессмысленна.

[Druu]

> Хотелось бы понять что Вас смущает. Тоже самое происходит в алгоритмах с ОПН.

А вот и неправильно. При преобразовании в ОПН каждый символ _ровно один раз_ попадает на вход алгоритма, _ровно один раз_ на стек попадает (если считать «удерживание» операции попаданием на стек, иначе она и раза не попадает) и _ровно один раз_ из стека достается. То есть если у вас 100 символов на входе — вы сто раз получите символ на вход, сто раз положите на стек и сто раз достанете (ну по факту даже меньше, это оценка сверху). Сравните со своим алгоритмом теперь.

> А в регулярных выражениях можно было бы попробовать механизмы поиска фрагмента текста.

Вы очень удивитесь сейчас, видимо, но регулярные выражения именно через сравнение символов и работают.

[valerar]

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

А вот и неправильно. При преобразовании в ОПН каждый символ _ровно один раз_ попадает на вход алгоритма, _ровно один раз_ на стек попадает (если считать «удерживание» операции попаданием на стек, иначе она и раза не попадает) и _ровно один раз_ из стека достается.

Ладно, давайте разберёмся.
Несколько вводных замечаний (я уже осторожничаю)
1. Рассматриваем весь алгоритм от прихода инфиксной строки до получения конечного результата.
2. Операнды являются вещественными числами с длиной >=3
3. Алгоритм двухстековый (операнды отдельно, операции отдельно) как наиболее эффективный.
4. Попасть на вход алгоритма и быть задействованным в его работе — вещи разные, но мы их будем считать вместе.
5. Имеем 4 вида символов: 1. цифра 2. операция 3. "(" 4. ")" 5."." (разделитель) по видам логики обработки. Символы разделителей порядков игнорируем
6. Такие операции как нормализация по пробелам, валидация формулы и прочие сервисные игнорируем. Только чистый алгоритм.
7. s — общее количество использования
Поехали.
1. считывание символа в регистр АЛУ — 1
1.1 преобразовать в Сhar — (приведение типа) — 1
2. проверка на совпадение с одним из видов от 1 до 5 берём среднее — 3 (s — 4)
Здесь больше вообще-то, поскольку сравнение идёт с 17-ю символами
3. если цифра, то
3.1 записать в буфер числа (запись) — 1ц.
3.2 при приходе операции или ")" записать число в стек (чтение запись) 2ц
3.3 при расчёте операции вызов из стека запись в АЛУ 2ц
4. если операция, то
4.1 проверить приоритет по отношению к предыдущей операции (сравнение) — 2о (по одной на каждое положение проверяющий-проверяемый)
4.2 если приоритеты равны, то
4.2.1 предыдущий отправляется в АЛУ на расчёт (чтение) -1о
4.2.2 текущий записывается в стек операций (запись) — 1о
4.2.3 ИНАЧЕ текущий записывается в стек операций (запись) — 1о (1о-)
4.2.4. при расчёте операции вызов из стека запись в АЛУ 2о
5. если "(", то отправляется в стек операций (запись) — 1с
5.1 при завершении реверса удаление 1с
6. если ")", то
6.1 запустить реверс на расчёт фрагмента (удаление) — 1с
7. если ".", то записать в буфер числа (запись) — 1т.
7.1 при приходе операции или ")" записать число в стек (чтение запись) 2т
Может что еще забыл, ну да бог с ним. забудем пока перезапись вызов результатов, приведение чисел к формату dubl. Поведём итог
Обращение символам в процессе выполнения алгоритма
к любому — 5
дополнительно:
к цифре — 5
к операции — 6
к "(" — 2
к ")" — 1
к "." — 3
Таким образом общее число обращений к символу
к цифре — 10 (без учёта операций по результатам)
к операции — 11
к "(" — 7
к ")" — 6
к "." — 8
чтобы привести к сравнимому результату возьмём строку 100 символов. Из них при 8 закрытых скобками фрагментах получаем
"(" — 8 — 64 обращения
")" — 8 — 64 обращения
100-16 = 84 символа
84/4 = 21 групп операнд+операция
Операции — 20 — 220 обращений
цифры и точки — 64
"." — 21 — 168 обращений
цифры — 43 — 430 обращений
таким образом на строку в 100 символов общее количество обращений — 946

Сравните со своим алгоритмом теперь

Здесь сложнее считать, поскольку плохо понятно сколько обращений проходит в операциях со StringBuilder и с регулярными выражениями. Также как выше отбросим обращения при перезаписи результатов. Чтобы рассчитать количество проходов при выделении фрагментов по скобкам, \\ ?? поскольку выделенные фрагменты сразу удаляются возьмём коэффициент 1.5 к исходной длине строки.
Получаем
1. поиск первой ")" сильно зависит от месторасположения. С учётом исходных данных, 8 групп, максимальное расположение от начала первой ")" составит 92 символ. Из них
"(" — 8
операции — 20
цифры — 43
"." — 21
общее число обращений за проход — 92
2. Реверс. Поиск первой ")" при средней длине фрагмента 21 символ получим 21 обращение
3. Копирование фрагмента в строку «фрагмент» (чтение-запись) 42 обращения (копирование не по символам, ну да бог с ним). (допускаем: на фрагмент 6 операций, 2 *, 1/, 2+, 1-.) (суммарно по операциям — 119)
4. блок умножения (сумарно — 49 обращений)
4.1 Поиск первой операции * (допускаем: на фрагмент 7 операций, 2 *, 1/,2+,1-.
1-й * на 7 поз.) — 7обращений. (сум=23)
4.1.1.выделение левого фрагмента 3*2 (так же как в ОПН по видам и по среднему) 6 обращений.
4.1.2. выделение правого операнда 2*2 = 4 обращений
4.1.3. расчет результата, запись результата 6 обращений
4.2. Поиск второй операции * (Вх -18, с конца правого операнда(7), позиция* 15) — 8 обращений. (сум=26)
4.2.1.выделение левого фрагмента 3*2 (так же как в ОПН по видам и по среднему) 6 обращений.
4.2.2 выделение правого операнда 3*2 = 6 обращений
4.2.3. расчет результата, запись результата 6 обращений
5. Блок деления (Вх -15 симв, операция на 3) (сумарно — 17 обращений)
5.1 Поиск первой операции / 1-й / на 3 поз.) — 3 обращений.
5.1.1.выделение левого фрагмента 2*2 (так же как в ОПН по видам и по среднему) 4 обращений.
5.1.2. выделение правого операнда 2*2 = 4 обращений
5.1.3. расчет результата, запись результата 6 обращений
6. Блок сложения /вычитания (Вх -12 симв, ) (сумарно — 53 обращений)
5.1 Поиск первой операции (Вх12 с., на 3 поз.) — 3 обращений. (сумм=17)
5.1.1.выделение левого фрагмента 2*2 (так же как в ОПН по видам и по среднему) 4 обращений.
5.1.2. выделение правого операнда 2*2 = 4 обращений
5.1.3. расчет результата, запись результата 6 обращений
5.2 Поиск второй операции (Вх-9 на 4 поз.) — 3 обращений. (сум=17)
5.2.1.выделение левого фрагмента 2*2 (так же как в ОПН по видам и по среднему) 4 обращений.
5.2.2. выделение правого операнда 2*2 = 4 обращений
5.2.3. расчет результата, запись результата 6 обращений
5.3 Поиск третьей операции (Вх-6 на 3 поз.) — 3 обращений. (сум=19)
5.3.1.выделение левого фрагмента 2*2 (так же как в ОПН по видам и по среднему) 4 обращений.
5.3.2. выделение правого операнда 3*2 = 6 обращений
5.3.3. расчет результата, запись результата 6 обращений
Осталось 7 фрагментов. Примем что у них всё по столько же. итого 833
В указанной конфигурации исходной строки далее будет только реверс. Так что ещё 7*21= 147
Итого: 1254
Итак, вроде как всё понятно ОПН — 946, П-П -1254 обращений. Однако вспоминаем что здесь нигде не учтена логика, мои оценки количества обращений весьма сомнительны, ну и прочие, влияющие на производительность, вещи.
Методику расчёта оставил специально, чтобы не было вопросов.
Если честно, я ожидал худших результатов для П-П. А так… Даже почти близко.

[Druu]

> 1. поиск первой ")" сильно зависит от месторасположения. С учётом исходных > данных, 8 групп, максимальное расположение от начала первой ")" составит > 92 символ. Из них
> "(" — 8
> операции — 20
> цифры — 43
> "." — 21
> общее число обращений за проход — 92

Не-не-не, так дело не пойдет. Вы же в ОПН расписываете в виде «положить на стек», «положить в АЛУ» и тд.

Извольте в тех же операциях описать и ваш «поиск», то есть — как минимум, каждый символ надо считать в АЛУ (2) и проверить на совпадение со скобкой (1), это 3. Значит, общее число обращений за проход: 92*3 = 276. Аналогично, поиск левой "(" — в среднем 63 обращения. Или, у случае поиска операций — почему вы не учитывается по 4 на символ? Ну и так далее. Извольте пересчитать. А вообще, для начала просто попробуйте записать ваш алгоритм в полной форме, раскрыв все эти «поиски», «регекспы» и прочее. И вы поймете, что он а порядок сложнее, чем оригинальный.

[valerar]

Да нет, я пожалуй воздержусь от таких экспериментов.
Лучший критерий — результаты натурного испытания, но этим я сейчас тоже заниматься не буду.
будем считать историю завершённой.

[Druu]

> Да нет, я пожалуй воздержусь от таких экспериментов.

То есть, ваш алгоритм настолько сложен, что вы даже не в состоянии его описать, в отличии от преобразования в ОПН?

> будем считать историю завершённой.

Как я понимаю, вы осознали, что и при теоретических расчетах и при натурных испытаниях, ваш алгоритм даст просадку на десятичные порядки.

[valerar]

Хм-м… А я думал здесь без тролей обойдётся. Не обошлось.

[Druu]

> А я думал здесь без тролей обойдётся. Не обошлось.

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

[zagayevskiy]

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

[Zenitchik]

А все остальные пытаются научить Джима французскому.

[picul]

здесь нигде не учтена логика

Это Вы правильно подметили. А еще не учтена реальная архитектура компьютерных систем.

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

[picul]

безальтернативность решения ОПН в информационной сфере

прочитал с десяток, отбросив рекурсию и деревья. Только ОПН

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

[valerar]

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

[picul]

Рекурсивный спуск замечательно подходит в этом случае, и в понимании очень прост ( хотя это конечно субъективно ). И, между прочим, именно спуск, а не ОПН, был первым подходом, примененным мной для решения данной задачи.

[valerar]

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

[ainoneko]

Мы используем инфиксную форму, как мне кажется лишь потому, что так исторически сложилось.

А японцы вообще на Форте разговаривают. Ну почти.
(Ну и в клингонском кое-где тоже что-то есть: «Foo and Bar» будет «foo bar 'ej»)

[zagayevskiy]

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

[valerar]

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

[zagayevskiy]

Конечно не сняли. Но, в целом, понятно, что слились. Все отсылки в сторону обучения — бред, никакой пользы от этого велосипеда нет. "Непонимание", что смотреть, отнесём к упёртости и неспособности видеть дальше своего носа.

[valerar]

Конечно не сняли. Но, в целом, понятно, что слились.

Какие остались вопросы? В чём выразилось «слились»?

никакой пользы от этого велосипеда нет.

Время покажет.

«Непонимание», что смотреть, отнесём к упёртости и неспособности видеть дальше своего носа.

Некорректно. У вас там нет комментариев что есть что, а бегать по всем вашим опусам желания не возникает. Укажите конкретно про что говорили и я посмотрю.
А про нос вам стоило бы быть осторожнее.

[Deosis]

Судя по коду парсера, вы используете рекурсивный спуск, и приоритеты операций зашиты в структуре методов.

[zagayevskiy]

И?..

[zagayevskiy]

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

[zagayevskiy]

т.е. нагляднее для функции суммы произвольного числа элементов «сумм(100; 232; 25+45)» преобразовать в «100;23;2;;45;25;+;3; сумм» -> «100;46;70;3; сумм»?

Примерно да, только то, что вы обозначили стрелкой, так выглядеть не будет. Будет стек (сверху вниз) 3, 70, 46, 100 и в потоке входа "сумм". Интерпретатор видит сумм, достаёт из стека верхний элемент (3) — и достаёт из стека же 3 элемента, далее суммируя их.

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

[zagayevskiy]

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

[Zenitchik]

Например, в POST-script процедуры, которые нужно положить в стек (тип данных такой у него есть — «процедура»), а не выполнить немедленно, заключаются в {}.