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

23.02.09

Разработка - Математика и алгоритмы

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

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

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

сабж...

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1754    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4416    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7460    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7855    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8837    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7803    dusha0020    8    

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

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

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

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

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

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

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