Алгоритм и функции Dijkstra

StackOverflow https://stackoverflow.com/questions/2949805

Вопрос

Вопрос: Предположим, у меня есть функция ввода, как sin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B) Указанный с BNF, я буду анализировать вход, используя рекурсивный алгоритм спуска, а затем, как я могу использовать или изменить алгоритм Dijkstra, чтобы обработать эту заданную функцию? Мне нужно выполнить его с грехом | COS |. SQRT |. Л.Н., где алгоритм Дейкстры должен сделать работу.

Редактировать: Может быть, я должен спросить также: какова лучшая практика или структура данных для представления заданной функции?

Редактировать: набор ввода может быть получен как:

C 0.01 .01 .02 .04 .08 .02 .02 .04 
A .016 .008 .116 .124 .147 .155 .039 .023  
D .012 .025 .05 .1 .1 .1 .025 .012000 .012
B .007 .007 .015 .022 .029 .036 .044 .051 .058 .066 .073 .080

Редактировать: шунтирующий двор - это алгоритм, чтобы преобразовать функцию ввода в RPN, но как я могу продлить его, чтобы принять другую функцию, как SIN | COS |. SQRT |. Л.Н.? Обеспечивает ли рекурсивный спуск требуемого расширения для шунтирования?

Это было полезно?

Решение

Я полагаю, вы говорите о Dijkstra's Шунтирующий двор алгоритм?

Для оценки обозначения обратного польского языка (вывод шунтирования) используется нормально стек.

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

Вот пост блога, который объясняет его более подробно: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunning-iard-algorithm-toLoallow-Variable-Numbers-of-arguments-Tom-functions/

Другие советы

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

В вашем случае вы говорите о рекурсивном пашстере спуска, что имеет втурию LL (K), и он определяется грамматикой, похожей на

expression ::= term + term | term - term
term ::= factor * factor | factor / factor
factor ::= ident | number

number ::= digit | digit number
digit ::= 0 | 1 | 2 ...

лучшая структура данных для хранения этой информации обычно является Абстрактное синтаксическое дерево Это дерево, которое реплицирует структуру кода, который он анализирует. В вашем примере вам понадобится другая структура или класс для различных кусков кода: BinaryOperation, Ident, Number, UnaryOperation, FunctionCall заканчиваясь иметь что-то вроде

                         BinaryOperation +
                          |            |
                                     BinaryOperation *
                                      |            |
                                    Number       BinaryOperation +
                                      |           |
                                     0.756     BinOp *
                                               |    |
                                             Ident Ident
                                               |    |
                                               C    D

Редактировать: не знал, что шунтинг-двор был изобретен Dijkstra! Кстати это довольно простой алгоритм, как объяснил иброн .. Ты никогда не перестанешь узнать что-то новое!

Использовать Antlr С грамматикой, аналогичной одному Джеку. Достаточно для создания хорошего парсера на нескольких языках: Java / C / C ++ / Python / etc. Прочитайте некоторые пример и учебные пособия. Вы должны использовать AntLRworks для более быстрой проверки выражения.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top