問題タブ [shunting-yard]

私は Jesse Brown の shunting yard アルゴリズム実装の修正版を使用しています。変数に double 値を代入する代わりに、基本的に記号演算を実行するように変数システムを変更しようとしています。たとえば、単純に pi = 3.14 と記述する代わりに、ソリューションに pi を含めるだけにしたいと考えています。したがって、1+2+pi は 3+pi になります。

コードは次のとおりです。私はそれをいじり始めたばかりで、多くのことをしていません。誰にもアイデアはありますか？

だからここに私のコードがあります：

ネストされた if ステートメントの if(operators.peek().equals... ビットが EmptyStackException を返すというエラーが発生し続けます。ポップされた数値 (endNumber) をキャストして返そうとすると、別のエラーが発生します。それを double としてキャストすると問題が発生します。

誰かがこれを見て、何が問題なのか、問題を解決する方法を教えてくれたら、それは素晴らしいことです。

Divert[i].equals("+")/("-") を削除すると、最初のエラーの問題が解決することはわかっていますが、それは私がやっていることにはあまり影響しません。

次の (中置) 式が与えられた場合:

次の 4 つの中置記法を作成したいと思います。

したがって、基本的に、すべての OR を取り除きたいと思います。

私はすでに最初の式の後置記法を持っているので、現在それを処理して目的の記法を取得しようとしています。ただし、この特定の状況は問題を引き起こします。

(説明のために、このクエリの接尾表記は次のようになります:)

これを達成するためのアルゴリズムを知っている人はいますか?

トークン )、(、|、*、+、-、/、変数、および定数を含む式のパーサーを作成しています。

これまでのところ、私のコードは *,/,-,+,(,) で動作しますが、絶対値を処理する方法がわかりません。

括弧を使用して、( で始まり ) で終わる、これは非常に単純ですが、どの "|" かをどのように判断すればよいでしょうか。はオープニングで、どちらがクロージングですか?

構文解析には、2 つのスタックと分流場アルゴリズム (または、少なくとも私が理解して記述した方法) を使用します。

一般に、中置数式を評価するプログラムは、Shunting Yard Algorithmのいくつかのバリエーションを使用して、最初に式を逆ポーランド記法に変換し、次に逆ポーランド記法を評価して単一の最終値を取得します。

私の質問は、INFIX -> RPN ステップをバイパスし、再帰的な降下解析を使用して、最初のインフィックス式を適切に評価するよく知られたアルゴリズムがあるかどうかです。

おそらく、INFIX -> RPN を変換するコンパイラまたはパーサーを作成するときに役立つ可能性があります。RPN は、式 (AST) の「コンパイルされた形式」の一種であり、単純な出力スタックを使用してコンピューターでより簡単に評価できます。しかし、単に中置式を数値出力値に即座に変換するコードを書いているだけの場合は、中間の RPN 形式をキャッシュする必要がないかもしれません。

それで、最初にRPNに変換せずに中置式を解析するためのよく知られたアルゴリズムはありますか? それとも、一般的に、RPN への変換は他のどのアプローチよりも効率的ですか?

以下のような表現があります。

許可される演算子は OR と AND で、括弧を使用して式をネストできます。PHP 5.3 で実装された Shunting Yard アルゴリズムを使用して、この文字列をトークン化し、抽象構文木 (AST) に変換することができました。上記の式の結果は次のようになります。

このツリーをトラバースするとき、ユーザーが選択できる数値の最終的な組み合わせを出力したいと考えています。与えられた表現では、これは不可能です。私が必要とするのは、実際には分配法則が適用された後のフォームです。

&-operator ノードとして許可されているノードは、リーフを運ぶ最後のノードだけであると結論付けました。他のすべては |-operator ノードでなければなりません。

上記で説明した文法を使用して任意の AST を、すべての最終順列を表すものに変換する方法は? 中置表現のトークンに分配法則を適用する方がよいでしょうか? ツリーの代わりに RPN 表現を使用する方が簡単ですか?

また、次のようなより難しい例があることにも注意してください。

結果として欲しいのは：

別の (より複雑な) 例として、左側のサブツリーと右側のサブツリーを切り替えるか、別の &-node を 1003 => 1003 1009 & の代わりに追加します。

私がすでに試したこと: 何度もグーグル検索し、ツリーの前後の順序をトラバースし、成功しなかったアルゴリズムを見つけようとしました。

正しい方向へのヒントや指針に感謝します。

私はJavaを学ぶために電卓をコーディングしています。私は最近、これに非常によく似たShunting Yardアルゴリズムをコーディングしました。私のアルゴリズムとリンクされたアルゴリズムの唯一の違いは、指数演算子も含まれていることです。変更点は次のとおりです。

と：

他のすべては同じです。

ただし、私はJavaとデータ構造に非常に慣れていないため、次のことがわかりません。

1. Shunting Yard アルゴリズムを Calc クラスに実装する方法。
2. アルゴリズムによって提供される接尾辞の処理を開始する方法。

これら 2 つの問題、またはその他の問題に関するアドバイスや例を教えていただければ幸いです。

以下は、私の電卓の元のコードのフレームワークです。これは、2+2. コメントは、Shunting Yard アルゴリズムの実装を開始するための私のアイデアですが、正しい方向に進んでいるかどうかはわかりません。コメントは、その上/下の特定の行を置き換えます。このコードのどの程度がまだ使用可能かはわかりません。

ありがとう！

避難所のアルゴリズムで忙しいです。次のような表現がある場合:

クラスは、変数の名前と値が何であるかを知りません。だから私は呼び出しでクラス、instantianteVariable(char name, int value) に関数を持っています:

式の未知の変数を現在既知の変数に置き換えるにはどうすればよいですか? x と y は任意の文字である可能性があるため、x と y という名前のクラス メンバーを作成することはできません。

私は現在、変数で機能するシャンティング ヤード アルゴリズムの修正版に取り組んでいますが、それを機能させる方法がわかりません。たとえば、アルゴリズムで 2 * (2x + 5) - 5 を 4x + 5 に書き換えたいと思います。これを既に実行している既に実装されているアルゴリズムへのアイデア/リンクはありますか?