gifts2017

Перевод выражения из инфиксной записи в постфиксную (польская запись)

Опубликовал Ярослав Радкевич (WKBAPKA) в раздел Программирование - Практика программирования

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

сабж...

Скачать файлы

Наименование Файл Версия Размер Кол. Скачив.
-
.1235336747 7,43Kb
25.09.09
63
.1235336747 7,43Kb 63 Бесплатно

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Sheridan (WKBAPKA) 23.02.09 00:12
На этапе лексического анализа не все ошибки в выражении отлавливает, но сама идея думаю будет понятна и интересна для тех кого эта тема интересует с практической точки зрения для реализации в собственных проектах
2. Sheridan (WKBAPKA) 23.02.09 00:14
Работает только с выражениями без применения переменных, т.е. только числовые константы, скобки, а также разделители выражения *-+/
3. Sheridan (WKBAPKA) 23.02.09 00:15
ДопустимыеСимволы.Добавить("(","2");
ДопустимыеСимволы.Добавить(")","2");
ДопустимыеСимволы.Добавить("*","1");
ДопустимыеСимволы.Добавить("/","1");
ДопустимыеСимволы.Добавить("+","1");
ДопустимыеСимволы.Добавить("-","1");
ДопустимыеСимволы.Добавить("^","1");
ДопустимыеСимволы.Добавить(".","3");
4. Василий Демидов (Душелов) 23.02.09 00:22
А поподробнее. Для чего это?
5. Sheridan (WKBAPKA) 23.02.09 00:30
пообсчаться :) на эту тему
6. Василий Демидов (Душелов) 23.02.09 01:34
Общаемся. :)
Ааа.... Начинаю понимать...

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

Например, рассмотрим вычисление выражения 7 2 3 * - (эквивалентное выражение в инфиксной нотации: 7-2*3).
Первый по порядку знак операции — «*», поэтому первой выполняется операция умножения над операндами 2 и 3 (они стоят последними перед знаком). Выражение при этом преобразуется к виду 7 6 - (результат умножения — 6, — заменяет тройку «2 3 *»).
Второй знак операции — «-». Выполняется операция вычитания над операндами 7 и 6.
Вычисление закончено. Результат последней операции равен 1, это и есть результат вычисления выражения.

Очевидное расширение обратной польской записи на унарные, тернарные и операции с любым другим количеством операндов: при использовании знаков таких операций в вычислении выражения операция применяется к соответствующему числу последних встретившихся операндов.
Anything; +1 Ответить
7. Сhe Burashka (CheBurator) 23.02.09 02:10
по такому стековому принципу кучу программируемых калькуляторов работало и работает и плюс к этому по-моему на на такой записи Forth работает...
8. Vasily Kushnir (vasilykushnir) 23.02.09 09:15
(7) Абсолютно верно. Форт собственно и есть стековый язык. По такому же принципу работают скрипты в планировщике nnCron (наследие Форт).
9. Sheridan (WKBAPKA) 24.02.09 09:56
я счаз штудирую книгу по технологии построения компиляторов... эта тема меня еще с детства интересует... у меня нет желания писать свой компилятор, т.е. приблуду которая еще будет и выполнять компеляцию в исполняемый код, но есть желание разобраться с придуманными технологиями, т.к. такие знания очень полезны во многих проектах...
насколько я понял, метод польской записи и стековый алгоритм широко распространен даже в современных языках программирования?!
10. Александр Рытов (Арчибальд) 24.02.09 11:36
(9)Напрашиваются функции ВСтек(Значение) и ИзСтека() - и далее по штудируемой книжке. А стеки - это лучшее, что придумано для вычисления выражений. В той или иной форме они присутствуют практически во всех компиляторах и интерпретаторах. Например, в 1С.
11. Sheridan (WKBAPKA) 25.02.09 10:00
Да, это верно, эту обработачку я писал, что бы уже на практике посмотреть, как это будет работать :), поэтому написано не оптимально и по ходу там есть не большая ошибка, вроде, надо еще посмотреть...
12. Михаил Кащенко (mick_777) 20.08.09 17:54
я еще на 2-м курсе на паскале писал нечто похожее
только еще можно было указывать функции типа синусы и т.д., 2 переменные
а также делать затем вычисления

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

но для 1с это все ерунда, т.к. можно вызвать метод вычислить

толк есть в разборе выражений другого типа
например разбор нестандартного формата файла с применением конечных автоматов стекового типа. В 1С мне такое приходилось делать.
13. Ярослав Радкевич (WKBAPKA) 20.08.09 18:51
согласен, однако не всегда можно использовать "вычислить". но меня интресует это с научной точки зрения ;)
14. Роман (srv7) 21.04.10 19:22
задумка хорошая, сам хотел написать )
но не пашет: на вход дал строку "1+2*(3-4)+5", на выходе получилось " 1 2 3 4 - * + 5", что не есть правда... при попытке вычислить выражение в польской нотации будет ошибка ))) похоже последний символ обрезается
15. Алексей Комаров (q4a) 17.07.15 09:54
(14) srv7, да, должно получаться "1 2 3 4 - * + 5 +"
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа