9

C ++またはC＃のいずれかを使用する場合、逆ポーランド記法を「通常の」数学表記に解釈する方法はありますか？私はエンジニアリング会社で働いているので、彼らは時々RPNを使用し、それを変換する方法が必要です。助言がありますか？

4

7 に答える 7

15

はい。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)。そのため、右結合演算子の場合、括弧を避けるために、左側の分岐を (同等以上ではなく) 優先順位を高くする必要があります。

-また、 and/演算子の右側のブランチにもブラケットが必要であると考えられます。

于 2008-09-22T06:22:55.877 に答える
4

分流ヤード アルゴリズムは、Infix (つまり、代数) を RPN に変換するために使用されます。これはあなたが望むものの反対です。

RPN 入力の例を教えてください。私はベテランの HP 電卓ユーザー/プログラマーです。すべての入力と演算子を含むスタックがあると思います。式ツリーを再構築してから、ツリーをトラバースして中置式を生成する必要があると思います。

于 2008-09-22T06:24:15.717 に答える
2

C# には、逆ポーランド記法 (RPN) を解析するためのサポートが組み込まれていません。独自のパーサーを作成するか、オンラインで見つける必要があります。

後置形式 (RPN) を中置式 (代数方程式) に変換するためのチュートリアルが多数あります。thisを見てください。おそらく、それが便利であることがわかります。特定の後置表現には複数の中置記法が存在する可能性があることに注意してください。postfix から infix への変換について実際に議論している有用な例はほとんどありません。これは、私が非常に役立つと思った 2 部構成のエントリです。また、いくつかの疑似コードもあります。

于 2008-09-22T06:21:53.867 に答える
1

Ruby が読める場合は、ここでこれに対する適切な解決策を見つけることができます。

于 2008-09-22T06:28:53.957 に答える
0

1 つのアプローチは、中置記法から後置記法に変換するパーサーの書き方を説明しているドラゴンブックの第 2 章の例を取り上げ、それを逆にすることです。

于 2008-09-22T06:25:32.280 に答える
0

RPN (後置記法) から「通常の記法」(中置記法) に変換しようとしているソース テキスト (文字列) がある場合、これは確かに可能です (あまり難しくない可能性があります)。

RPN は、スタックベースのマシン用に設計されました。これは、操作が表される方法 ("2 + 3" -> "2 3 +") が、ハードウェア上で実際に実行される方法 ("2" をスタックにプッシュし、"3 をプッシュする") に適合するためです。 " をスタックに追加し、上位 2 つの引数をスタックからポップして追加し、スタックにプッシュします)。

基本的に、「リーフ ノード」で操作する 2 つの式と、その後の「親ノード」である操作自体を作成して、RPN から構文ツリーを作成します。これはおそらく、入力文字列を再帰的に調べることによって行われます (部分式がまだ正しく括弧で囲まれていない場合は、明確にするために部分式が正しく括弧で囲まれていることを確認する必要があります)。

その構文ツリーを取得したら、そのツリーの前順、後順、または順序どおりのトラバーサルを実行するだけで、プレフィックス、インフィックス、またはポストフィックスの表記を出力できます (ここでも、必要に応じてわかりやすくするために出力を括弧で囲みます)。

詳細については、こちらを参照してください。

于 2008-09-22T06:26:28.160 に答える
0

私は Java でバージョンを書きました。それはここにあり、Objective-Cのバージョンはここにあります。

可能なアルゴリズム: ユーザーが 8、9、* などと入力するように、rpn に入力を含むスタックがあるとします。最初から最後まで配列を反復処理し、常に現在の要素を削除します。あなたが評価するこの要素。オペランドの場合は、結果スタックに追加します。演算子の場合、オペランドに対して結果スタックを 2 回ポップし (2 項演算の場合)、結果スタックに結果文字列を書き込みます。

" 8, 9, +, 2, * "の入力例を使用すると、resultstack でこれらの値を取得できます (角括弧は単一の要素を示します)。

ステップ 1: [8]

ステップ 2: [8]、[9]

ステップ 3: [(8 + 9)]

ステップ 4: [(8 + 9)]、[2]

ステップ 5: [(8 + 9) * 2]

入力スタックが空になると、作業は終了し、resultStack の唯一の要素が結果になります。(ただし、入力には、「+ 2 3 /」などの先頭の操作のように、意味をなさない複数のエントリまたはそのようなものが含まれる可能性があることに注意してください。)

リンク内の実装では、演算子やオペランドなどの自作の型を意図的に使用したり、複合パターンなどを適用したりしません。クリーンでシンプルなので、簡単に理解して他の言語に移植できます。

C# への移植は簡単です。

于 2012-05-08T22:33:53.253 に答える