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

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

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

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

EDIT: Шунтирование Ярд алгоритм для преобразования функции входа в RPN, но как я могу продлить его принять другую функцию, как грех | cos | sqrt | пер? Предоставляет ли рекурсивный спуск необходимое расширение для Shunting Yard?

источник

2010-06-01 baris.aydinoz

Я не вижу, какой алгоритм dijkstra имеет отношение к разбору выражения. Вы хотите узнать расстояние между узлами в дереве разбора? Если да, зачем? – sepp2k

@ sepp2K: Это не связано с разбором, я буду анализировать с использованием рекурсивного спуска, но проблема заключается в выполнении этой функции с переменными входами. –

@baris_a, после того, как вы построили дерево синтаксиса, вы можете оценить его с помощью (обычно) рекурсивной функции 'eval'. –

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

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

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/

источник

2010-06-01 14:23:48

Shunting Yard - это алгоритм преобразования входной функции в RPN, но как я могу расширить ее, чтобы принять другую функцию, такую как sin | cos | sqrt | пер? Предоставляет ли рекурсивный спуск необходимое расширение для Shunting Yard? –

@Baris_a: Я отредактировал ответ, чтобы добавить еще одну ссылку. Рекурсивный спуск и Шунтирующий двор - это два отдельных метода для синтаксического анализа. –

@Moron: Спасибо за ссылку на переменный ввод, но проблема sin2 cos | sqrt | ln отличается, я просто не понимаю, мне нужно обрабатывать эти функции в другом стеке? Поскольку они не являются операторами, ни выводами. –

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

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

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

EDIT: Не знал, что маневровый двор был изобретен Дейкстра! Кстати, это довольно простой алгоритм, как объяснил Морон .. вы никогда не перестанете изучать что-то новое!

источник

2010-06-01 12:59:43 Jack

может ли downvoters быть достаточно любезным, чтобы объяснить себя? спасибо, за лучший мир :) – Jack

Dijkstra придумал много чего. Остальные из нас просто смертные. –

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

источник

2010-06-01 21:28:27 INS

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

ответ

Смежные вопросы