Алгоритм и функции Дейкстры - PullRequest
Новая
       38

Алгоритм и функции Дейкстры

0 голосов
/ 01 июня 2010

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

РЕДАКТИРОВАТЬ: Может быть, я должен также спросить: Какова наилучшая практика или структура данных для представления данной функции?

EDIT: входной набор может быть получен как: 

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

РЕДАКТИРОВАТЬ: Shunting Yard - это алгоритм для преобразования входной функции в RPN, но как я могу расширить его для принятия другой функции, такой как sin | потому что | sqrt | пер? Обеспечивает ли рекурсивный спуск обязательное продление до Шунтирующего двора?

Ответы [ 3 ]

3 голосов
/ 01 июня 2010

Полагаю, вы говорите об алгоритме Дейкстры Маневровый двор ?

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

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

Вот запись в блоге, которая объясняет это более подробно: http://www.kallisti.net.nz/blog/2008/02/extension-to-the-shunting-yard-algorithm-to-allow-variable-numbers-of-arguments-to-functions/

0 голосов
/ 02 июня 2010

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

0 голосов
/ 01 июня 2010

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

В вашем случае вы говорите о парсере рекурсивного спуска, который имеет вид 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! Кстати, это довольно простой алгоритм, как объяснил Морон. Вы никогда не перестанете узнавать что-то новое!

...