0

問題は、BNF で指定されたような入力関数があるとsin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)します。再帰降下アルゴリズムを使用して入力を解析し、ダイクストラのアルゴリズムを使用または変更して、この特定の関数を処理するにはどうすればよいでしょうか? sin | で実行する必要があります。コス | 平方根 | ln では、ダイクストラのアルゴリズムが作業を行う必要があります。

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

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 | のような別の関数を受け入れるように拡張するにはどうすればよいですか? コス | 平方根 | ん？再帰降下は、Shunting Yard に必要な拡張を提供しますか?

4

3 に答える 3

3

Dijkstra のShunting Yardアルゴリズムについて話していると思いますか?

逆ポーランド記法（分流場の出力）を評価するために、通常、スタックが使用されます。

Shunting Yard は、Algol で解析を行うように考案されたものであり、任意の関数 (固定数または可変数の引数) で動作するはずだと思います。

これについて詳しく説明しているブログ投稿は次のとおりです。関数への引数の/

于 2010-06-01T14:23:48.107 に答える
0

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

編集：分流場がダイクストラによって発明されたことを知りませんでした！ちなみに、Moron が説明したように、これは非常に簡単なアルゴリズムです..新しいことを学ぶのをやめることはありません!

于 2010-06-01T12:59:43.190 に答える
0

Jack が提供したものと同様の文法でANTLRを使用します。複数の言語で優れたパーサーを作成するだけで十分です: Java/C/C++/Python/etc. いくつかの例とチュートリアルを読んでください。式の検証を高速化するには、 ANTLRWorksを使用する必要があります。

于 2010-06-01T21:28:27.907 に答える