Формулу из исходного вида (например, с доски) всё равно нужно (человеку) как-то перевести в строку.
Согласитесь что перевод с доски в строку — это уже другой алгоритм и мы здесь его не рассматривали исходно. Для перевода в инфиксную запись — это сгруппировать скобками числитель и знаменатель и трансформировать дробную черту в знак деления — всё. А для ОПН? (вопрос риторический)
Главное, чтобы функция та же самая была.
Вопрос в возможности представления одной постфиксной записи несколькими вариантами инфиксной.
у меня предложение закончить эту интересную тему, как не совсем относящуюся к основной теме статьи.
Давайте попробуем ещё раз.
1. символ "(" — что делаем? отбрасываем или в стек кладём?
2. символ «1» — что делаем? — цифра, надо бы в стек, но мы не знаем последует ли за ней ещё одна цифра или сразу операция. Так что делаем? Или у вас предусловие что цифра это всегда сразу число? Или вы предварительно уже прошлись по числам и поставили разделители? Тогда где разделители и их обработка? Можно опереться на следующий символ "+", но тогда алгоритм несколько другой и цифру надо куда-то временно сохранить. А если потом будет точка(разделитель разрядов)?
Ну вы же сами ниже согласились что и при преобразовании и при расчёте открывающая скобка используется. Иначе получается что сущность есть, а в названии мы её отрицаем.
вы не правильно написали… в ОПН это будет ABCD+-+
Возможно. Хотя насколько я понимаю там возможны варианты в зависимости от того, кто из последних операндов больше.
Но ведь это всё уже не так уж и принципиально.
Автор рассматривал целостные алгоритмы от получения входной строки до получения конечного результата. Сортировка в ОПН бессмыслена без расчёта результата ради которой она делалась.
Так дело-то в том, что можно трансформировать сразу в ОПН, без промежуточного скобочного вида.
Увы, не получится. Скобки тоже являются элементом алгоритма ОПН (открывающая скобка заносится в стек).
можно предложить задачу перевести формулу из ОПН в инфиксную запись со скобками.
Не получится. Поскольку уже потеряна значимая для инфиксной записи информация, то может возникнуть многовариантность результата. Особенно на одноприоритетных участках. Скобки выполняют дополнительную функцию фиксации внимания на фрагменте, выделения не арифметических, а смысловых групп. Вы не восстановите адекватно даже такое простое выражение как (A + B) — (C — D) из ABCD+_-_-
Ну я даже в статье привёл пример его работы, вообще-то. Я что-то неправильно отразил в его работе?
Он же элементарный. И сложность O(n).
А вот тут есть вопросы. Сколько-сколько условий и предусловий в нём учитывается.
Вы сами попробуйте чуть усложнить формулу и сами всё увидите. Особенно когда введёте вещественные числа и множественные вложенные скобки.
Спасибо за развёрнутый комментарий, теперь есть объект для рассмотрения.
Идея раз — польскую нотацию надо знать.
— согласен.
Она простая (никаких приоритетов, просто стек и операции)
Это не так. Сложность выражения и приоритеты определяются самим выражением, а не преобразованной уже его формой. Просто ОПН все сложности перекладывает на этап сортировки, который почему-то иногда пытаются забыть. Процесс вычислений тоже не так линеен, вспоминаем про скобки (открывающая лежит в стеке операций) и про приоритеты операций во фрагменте.
Теперь про алгоритм пинг-понг. Он воспринимается проще, но в нём есть фатальный недостаток — он постоянно бегает туда-сюда по строке и меняет её.
Бегает туда-сюда Пинг-Понг не более чем ОПН, ветвлений меньше, основная операция «поиск по маске» более удобна для конвейера. Единственно когда просмотр начинается с начала строки — это при послойном (по приоритетам операций) расчёте. В ОПН, в принципе, тоже самое, только метаний побольше.
вместо стека для алгоритма ОПН в пинг-понге используется чтение-запись из памяти размером со входные данные.
Это так только на этапе выделения фрагмента. По размеру Вы сильно ошибаетесь как в отношении Пинг-Понг так и в отношении ОПН. И там и там используется метод высечения фрагментов. Только в ОПН он вроде как скрытый, а в Пинг-Понг явный.
Чтение символа (каждого символа) в ОПН происходит из памяти, затем этот символ долго крутят, чтобы положить в нужное место, причём, в зависимости от предыстории, можно уйти и на расчёт и на укладывание в стек и на реверсивный расчёт фрагмента.
В Пинг-понг каждый символ не крутится в логике и считывается только при непосредственной потребности и то, не посимвольно для чисел и операций, а смысловой группой. Считывание операции и операндов из стеков, а затем укладывание результата снова в стек, может несколько и быстрее, но ничем не отличается от считывания операндов и операции из строки и замены фрагмента на результат расчёта.
может обрабатывать большие файлы, последовательно читая их байт за байтом без необходимости держать весь файл в оперативной памяти.
Во-первых, это заблуждение. Поставьте пару тройку глобальных скобок в начале выражения и сами увидите. Так что речь может идти только о логически завершённых кусках. Точно так же это можно делать и в Пинг-Понг.
его можно компоновать с другими обработчиками — например, собрать цепочку из алгоритмов — первый убирает комментарии из строки, второй — парсит числа и операции (чтобы потом не развлекаться сборкой числа из цифр), третий — преобразует в постфиксную нотацию, четвёртый тут же вычисляет результат.
Здесь, с моей точки зрения, вы уже пытаетесь вывести некоторые функции целостного алгоритма за его границы (сборка чисел). К тому же каких-либо ограничений на использование Пинг-Понг в сборке с другими алгоритмами я не наблюдаю.
Классический алгоритм не использует рекурсию. Вся память, что ему нужна — стек. Проще уже некуда.
Пинг-Понг как-то тоже рекурсию не использует. Вся память, которая ему нужна это входная строка (в ОПН тоже есть) и строка фрагмента (в ОПН стек, вернее ДВА стека). К тому же он избавлен от опасности переполнения стека.
Так что пока преимуществ ОПН, извините, пока не наблюдаю. Скоростная работа со стеком в ОПН с лихвой компенсируется накладными расходами на посимвольной аналитике, как в режиме сортировки, так и в режиме расчётов.
Проще уже некуда.
Я не утверждаю, поверьте, что ОПН плохой алгоритм, но по поводу его простоты, как мне кажется, Вы сильно преувеличиваете.
Нет, это не одинаково даже для алгоритмов в вашем представлении. В первом алгоритме есть строчка, перенесенная из вики «В стеке должны были остаться только символы операторов». Там еще есть продолжение "; если это не так, значит в выражении не согласованы скобки.". То есть здесь мы имеем контрольную точку проверки выражения на синтаксическую целостность, проверка выполняется до начала вычисления.
В вашем алгоритме такой проверки нет, вычисление начинается сразу со чтения первой переменной.
Ну в первом алгоритме только оценочное суждение: «должны были остаться» — это не фиксация этапа проверки.
В представленном алгоритме так же не выделяется этап проверки парности скобок, хотя он присутствует и да, до начала разбора строки. Но так же не присутствует проверка деления на ноль, хотя такая ситуация может просто возникнуть в процессе вычисления. Но я считал важным показать сам принцип, а не обвесы вокруг. Возможно в этом я и не прав.
А вот нет, не дам, поскольку строка — она и есть строка. Трансформация из вида, который мы видим на доске, к строке, которыми мы обмениваемся в машинном виде — это отдельная задача.
И это… как бы обойтись без холиваров?..
Да я только ЗА. Просто, поскольку статья моя, считаю необходимым отвечать по возможности всем. Было бы здорово если бы просто выяснили неточности, ткнули носом в ошибки — и всё. Но так почему-то не получается.
Странно… Вроде я уже на этот комментарий отвечал.
В двух словах.
1. Название верное. a+b, не тоже самое что ab+. Инверсия отношений налицо.
2. Алгоритм достаточно плохо воспринимаемый, требует серьёзного натаскивания.
3. Многие, в том числе и в умных книжках, упорно говорят об одном стеке, что сильно напрягает.
В статье не ставилась задача переучить кого-то. В первую очередь задачей было предложить более естественную альтернативу для изучения вопроса парсинга формул.
В статье — для честного сравнения на «входе» надо давать нормальные математические выражения с цепочками дробей и корней, не переведённые заранее в «скобочную» строчную форму, иначе получается что-то типа перевода удобных любимых круглых миль в вечно дробные километры.
Да пожалуйста: -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-тью вложенными на несколько уровней скобками. Имеет смысл?
Впрочем всё идёт к тому, что обе нотации в итоге останутся не у дел, а калькуляторы, а затем (не скоро да) и даже компиляторы будут понимать нормальную «бумажную» запись.
Да, похоже. Но алгоритм как-то надо было завершить, пусть и в упрощённой форме.
В тех программах, где я встречал ввод произвольного выражения и его вычисления, обычно выражение сначала полностью парсится до попытки его вычисления.
Ну а как вы будете его парсить отдельно от вычислений, в дерево раскладывать?
Если у вас синтаксически неправильное выражение, то ваш алгоритм часть выражения (и часть функций) выполнит, а часть нет — как бы это не то, что ожидается от компьютера.
Это одинаково для обоих алгоритмов. Некорректности приходится ловить не только во входной строке, но и возникающие в результате расчётов.
Простите, а «сортировочная станция» это тоже я придумал? (подражание известной фразе из к/ф «Кавказская пленница»)
Преобразование в ОПН выполняется за единственный проход элементарно
Чтобы не спорить бессмысленно вот вам формула: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W). Давайте разберём на её примере. Начало разбора приведено в статье. И просто посчитаем количество условий ветвления алгоритма в зависимости от предыдущей информации (даже не одного символа). Меня хватило только на одну скобку, может у вас получится лучше. Заодно посмотрим количество возвратов (метаний).
Вот тут не соглашусь, название точно определяет суть. Поместить знак операции ЗА операндами эти нисколько не естественно. a+b как-то отличается от ab+, не говоря уже о более сложных выражениях.
И да для преобразования «обычной» записи в Естественную Польскую Запись всегда использовался алгоритм с двумя стеками.
Почитайте гуру и многих комментаторов, очень часто речь идёт об одном стеке. И это сильно сбивает, когда сталкиваешься с этим впервые.
Не совсем так. Я выделю сначала фрагмент (a+b). рассчитаю и заменю, затем то же самое с (12+с). Затем просто считается вся остальная формула. Но в этом-то смысле алгоритмы практически не отличаются. В ОПН происходит тоже самое. Копировать многократно строку я как-то особого смысла не вижу. Так что требования по памяти в обоих алгоритмах практически не отличаются. А вот переполнение стеков в предложенной вами конструкции миллион символов и сто тысяч скобок очень сильно вероятно.
Да ладно, если на входе строка сразу в ОПН, то это уже не вопрос выбора алгоритма, но обычно всё же исходная строка представлена в инфиксной (обычной) форме.
Ваши аргументы неубедительны.
А вот это уже предмет для разговора. Здесь хотелось бы поподробнее.
Согласитесь что перевод с доски в строку — это уже другой алгоритм и мы здесь его не рассматривали исходно. Для перевода в инфиксную запись — это сгруппировать скобками числитель и знаменатель и трансформировать дробную черту в знак деления — всё. А для ОПН? (вопрос риторический)
Вопрос в возможности представления одной постфиксной записи несколькими вариантами инфиксной.
у меня предложение закончить эту интересную тему, как не совсем относящуюся к основной теме статьи.
1. символ "(" — что делаем? отбрасываем или в стек кладём?
2. символ «1» — что делаем? — цифра, надо бы в стек, но мы не знаем последует ли за ней ещё одна цифра или сразу операция. Так что делаем? Или у вас предусловие что цифра это всегда сразу число? Или вы предварительно уже прошлись по числам и поставили разделители? Тогда где разделители и их обработка? Можно опереться на следующий символ "+", но тогда алгоритм несколько другой и цифру надо куда-то временно сохранить. А если потом будет точка(разделитель разрядов)?
Ну и так далее…
Как видим всё не так просто.
Ну вы же сами ниже согласились что и при преобразовании и при расчёте открывающая скобка используется. Иначе получается что сущность есть, а в названии мы её отрицаем.
Возможно. Хотя насколько я понимаю там возможны варианты в зависимости от того, кто из последних операндов больше.
Но ведь это всё уже не так уж и принципиально.
Увы, не получится. Скобки тоже являются элементом алгоритма ОПН (открывающая скобка заносится в стек).
Не получится. Поскольку уже потеряна значимая для инфиксной записи информация, то может возникнуть многовариантность результата. Особенно на одноприоритетных участках. Скобки выполняют дополнительную функцию фиксации внимания на фрагменте, выделения не арифметических, а смысловых групп. Вы не восстановите адекватно даже такое простое выражение как (A + B) — (C — D) из ABCD+_-_-
А вот тут есть вопросы. Сколько-сколько условий и предусловий в нём учитывается.
Вы сами попробуйте чуть усложнить формулу и сами всё увидите. Особенно когда введёте вещественные числа и множественные вложенные скобки.
— согласен.
Это не так. Сложность выражения и приоритеты определяются самим выражением, а не преобразованной уже его формой. Просто ОПН все сложности перекладывает на этап сортировки, который почему-то иногда пытаются забыть. Процесс вычислений тоже не так линеен, вспоминаем про скобки (открывающая лежит в стеке операций) и про приоритеты операций во фрагменте.
Бегает туда-сюда Пинг-Понг не более чем ОПН, ветвлений меньше, основная операция «поиск по маске» более удобна для конвейера. Единственно когда просмотр начинается с начала строки — это при послойном (по приоритетам операций) расчёте. В ОПН, в принципе, тоже самое, только метаний побольше.
Это так только на этапе выделения фрагмента. По размеру Вы сильно ошибаетесь как в отношении Пинг-Понг так и в отношении ОПН. И там и там используется метод высечения фрагментов. Только в ОПН он вроде как скрытый, а в Пинг-Понг явный.
Чтение символа (каждого символа) в ОПН происходит из памяти, затем этот символ долго крутят, чтобы положить в нужное место, причём, в зависимости от предыстории, можно уйти и на расчёт и на укладывание в стек и на реверсивный расчёт фрагмента.
В Пинг-понг каждый символ не крутится в логике и считывается только при непосредственной потребности и то, не посимвольно для чисел и операций, а смысловой группой. Считывание операции и операндов из стеков, а затем укладывание результата снова в стек, может несколько и быстрее, но ничем не отличается от считывания операндов и операции из строки и замены фрагмента на результат расчёта.
Во-первых, это заблуждение. Поставьте пару тройку глобальных скобок в начале выражения и сами увидите. Так что речь может идти только о логически завершённых кусках. Точно так же это можно делать и в Пинг-Понг.
Здесь, с моей точки зрения, вы уже пытаетесь вывести некоторые функции целостного алгоритма за его границы (сборка чисел). К тому же каких-либо ограничений на использование Пинг-Понг в сборке с другими алгоритмами я не наблюдаю.
Пинг-Понг как-то тоже рекурсию не использует. Вся память, которая ему нужна это входная строка (в ОПН тоже есть) и строка фрагмента (в ОПН стек, вернее ДВА стека). К тому же он избавлен от опасности переполнения стека.
Так что пока преимуществ ОПН, извините, пока не наблюдаю. Скоростная работа со стеком в ОПН с лихвой компенсируется накладными расходами на посимвольной аналитике, как в режиме сортировки, так и в режиме расчётов.
Я не утверждаю, поверьте, что ОПН плохой алгоритм, но по поводу его простоты, как мне кажется, Вы сильно преувеличиваете.
Ну в первом алгоритме только оценочное суждение: «должны были остаться» — это не фиксация этапа проверки.
В представленном алгоритме так же не выделяется этап проверки парности скобок, хотя он присутствует и да, до начала разбора строки. Но так же не присутствует проверка деления на ноль, хотя такая ситуация может просто возникнуть в процессе вычисления. Но я считал важным показать сам принцип, а не обвесы вокруг. Возможно в этом я и не прав.
Да я только ЗА. Просто, поскольку статья моя, считаю необходимым отвечать по возможности всем. Было бы здорово если бы просто выяснили неточности, ткнули носом в ошибки — и всё. Но так почему-то не получается.
В двух словах.
1. Название верное. a+b, не тоже самое что ab+. Инверсия отношений налицо.
2. Алгоритм достаточно плохо воспринимаемый, требует серьёзного натаскивания.
3. Многие, в том числе и в умных книжках, упорно говорят об одном стеке, что сильно напрягает.
Да пожалуйста: -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-тью вложенными на несколько уровней скобками. Имеет смысл?
Вот здесь согласен полностью :)
Ну а как вы будете его парсить отдельно от вычислений, в дерево раскладывать?
Это одинаково для обоих алгоритмов. Некорректности приходится ловить не только во входной строке, но и возникающие в результате расчётов.
Простите, а «сортировочная станция» это тоже я придумал? (подражание известной фразе из к/ф «Кавказская пленница»)
Чтобы не спорить бессмысленно вот вам формула: (A+B*C/D)+(E-F*((G/(H-J*(-1)+I)-L*(M-N)-R)+S)*W). Давайте разберём на её примере. Начало разбора приведено в статье. И просто посчитаем количество условий ветвления алгоритма в зависимости от предыдущей информации (даже не одного символа). Меня хватило только на одну скобку, может у вас получится лучше. Заодно посмотрим количество возвратов (метаний).
Почитайте гуру и многих комментаторов, очень часто речь идёт об одном стеке. И это сильно сбивает, когда сталкиваешься с этим впервые.
А вот это уже предмет для разговора. Здесь хотелось бы поподробнее.