逆ポーランド記法の変換
https://stackoverflow.com/questions/113424
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
C++ または C# を使用するときに、逆ポーランド表記を「通常の」数学表記に解釈する方法はありますか?私はエンジニアリング会社で働いているため、RPN を時々使用するため、それを変換する方法が必要です。助言がありますか？
解決
はい。RPN 計算機がどのように機能するかを考えてみましょう。ここでは、値を計算する代わりに、操作をツリーに追加します。したがって、たとえば、 2 3 4 + *, + に達したら、スタックに 7 を置くのではなく、 (+ 3 4) スタック上にあります。そして同様に * に到達すると (スタックは次のようになります) 2 (+ 3 4) * その段階では)、となります。 (* 2 (+ 3 4)).
これは接頭辞表記なので、中置表記に変換する必要があります。深さを最初に、ツリーを左から右にトラバースします。各「内部レベル」で、演算子の優先順位が低い場合は、演算を括弧で囲む必要があります。そこで、あなたはこう言うでしょう。 2 * (3 + 4), + は * よりも優先順位が低いためです。
お役に立てれば！
編集：(上記では単項演算を考慮していないことを除けば) 微妙な点があります。私は左結合演算子を仮定しました。右連想の場合 (例: **)、その場合、異なる結果が得られます 2 3 4 ** ** ⇒ (** 2 (** 3 4)) 対 2 3 ** 4 ** ⇒ (** (** 2 3) 4).
ツリーから中置を再構築する場合、どちらの場合も優先順位に括弧で囲む必要がないことが示されていますが、実際には後者の場合は括弧で囲む必要があります ((2 ** 3) ** 4）。したがって、右結合演算子の場合、括弧で囲まれることを避けるために、左側の分岐の優先順位を (同等以上ではなく) 高くする必要があります。
また、さらに考えてみると、 の右側の分岐には括弧が必要です。 - そして / オペレーターも。
他のヒント
操車場アルゴリズムは、中置記号 (つまり、代数) から RPN へ。これはあなたが望んでいることとは逆です。
RPN 入力の例を教えていただけますか?私は HP 電卓のベテラン ユーザー/プログラマーです。すべての入力と演算子を含むスタックがあると思います。式ツリーを再構築し、ツリーを走査して中置形式を生成する必要があると思います。
C# には逆ポーランド記法 (RPN) の解析サポートが組み込まれていません。独自のパーサーを作成するか、オンラインで見つける必要があります。
後置形式 (RPN) を中置形式 (代数方程式) に変換するためのチュートリアルが多数あります。を見てみましょう これ, おそらくこれが便利だと思うでしょう。特定の後置表現に対して複数の中置表記が存在する可能性があることに留意しながら、後置式を中置形式に変換する「リバース エンジニアリング」を試みることができます。後置から中置への変換を実際に説明する有用な例はほとんどありません。これは私が非常に役立つと感じた 2 部構成のエントリです。いくつかの疑似コードもあります。
Ruby が読めるなら、これに対する良い解決策がいくつか見つかるでしょう。 ここ
1 つのアプローチは、 ドラゴンブック これは、中置記法から後置記法に変換し、その逆を行うためのパーサーを作成する方法を説明しています。
RPN (後置記法) から「通常の記法」 (中置記法) に変換したいソース テキスト (文字列) がある場合、これは確かに可能です (そしておそらくそれほど難しくはありません)。
RPN は、操作の表現方法 (「2 + 3」 -> 「2 3 +」) がハードウェア上で実際に実行される方法 (「2」をスタックにプッシュ、「3」をプッシュ) に適合するため、スタックベースのマシン向けに設計されています。 " をスタックに置き、先頭の 2 つの引数をスタックからポップして追加し、スタックに戻します)。
基本的に、操作する 2 つの式を「リーフ ノード」とし、その後に来る操作自体を「親ノード」にして、RPN から構文ツリーを作成します。これはおそらく、入力文字列を再帰的に調べることによって行われます (明確にするために部分式が正しく括弧で囲まれていない場合は、正しく括弧で囲まれていることを確認する必要があるでしょう)。
その構文ツリーを取得したら、そのツリーの前順序、後順序、または順序内の走査を実行するだけで、前置、中置、または後置表記を出力できます (ここでも、必要に応じて出力をわかりやすくするために括弧で囲みます)。
さらに詳しい情報が見つかります ここ.
Java でバージョンを書いたところです。 ここ もう 1 つは Objective-C で、 ここ.
可能なアルゴリズム:ユーザーが入力する rpn の入力を含むスタックがあるとします。8、9、*。配列を最初から最後まで反復処理し、常に現在の要素を削除します。この要素を評価します。オペランドの場合は、結果スタックに追加します。演算子の場合、オペランドの結果スタックを 2 回ポップし (バイナリ演算の場合)、結果の文字列を結果スタックに書き込みます。
「」の入力例では8, 9, +, 2, *" これらの値は結果スタックで取得されます (角括弧は単一の要素を示します):
ステップ1： [8]
ステップ2： [8], [9]
ステップ3: [(8 + 9)]
ステップ4: [(8 + 9)], [2]
ステップ5: [(8 + 9) * 2]
入力スタックが空になると作業は終了し、resultStack の唯一の要素が結果になります。(ただし、入力には、先頭の操作など、意味をなさない複数のエントリが含まれる可能性があることに注意してください。「+ 2 3 /」。)
リンク内の実装では、意図的に自作の型を使用していません。演算子やオペランドも適用されません。複合パターン。すっきりしていてシンプルなので、簡単に理解でき、他の言語にも移植できます。
C# への移植は簡単です。
