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 | LN、Dijkstraのアルゴリズムが作業を行う必要があります。

編集：私も尋ねるべきかもしれません：指定された機能を表すためのベストプラクティスまたはデータ構造は何ですか？

編集：入力セットは次のように取得できます。

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のような別の関数を受け入れるために拡張するにはどうすればよいですか| cos | SQRT | ln？再帰降下は、ヤードをシャントするために必要な拡張を提供しますか？

役に立ちましたか？

解決

私はあなたがディクストラについて話していると思います シャントヤード アルゴリズム？

逆ポリッシュ表記（シャントヤードの出力）を評価するために、通常はスタックが使用されます。

シャントヤードは、私が信じているアルゴルでの解析を行うために考案されました、そして、私はそれがあらゆる関数（固定または可変数の引数）で動作するはずだと思います。

これは、より詳細に説明するブログ投稿です。 http://www.kallisti.net.nz/blog/2008/02/extension-the-shunting-yard-algorithmto-Allow-Varbers-of-Arguments/-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によって発明されたことを知りませんでした！ちなみに、Moronが説明したような非常に簡単なアルゴリズムです。何か新しいことを学ぶのをやめることはありません！

使用する antlr 提供されたジャックに似た文法で。 java/c/c ++/python/etc：複数の言語で優れたパーサーを作成するのに十分なはずです。いくつかの例とチュートリアルを読んでください。使用する必要があります antlrworks より速い表現の検証用。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top