3

シャンティング ヤード アルゴリズムは、式を中置記法から後置記法 (逆ポーランド記法) に変換するために使用されるため、コンパイラによる評価が容易になります。たとえば、2 + 3 * 2に変換され2 3 2 * +ます。ウィキペディアでは、このアルゴリズムが次のような多くのアプリケーションで使用されていることが言及されています。

Forth、Factor、PostScript ページ記述言語、Befunge、Joy などのスタック指向プログラミング言語

C# や一般的な高水準言語さえ見当たりません。では、C# はこのアルゴリズムを式に使用するのでしょうか? いいえの場合、C# コンパイラは式をどのようにコンパイルして評価しますか?

4

1 に答える 1

4

はい、C# はスタック指向のプログラミング言語であるILに変換されます。コンパイラは、式を内部言語に変換するときに、RPN に続く操作のリストを作成します。

たとえば、このメソッド

int x(int a, int b, int c, int d) {
    return a+b*(c+d);
}

この内部言語に変換されます (何が起こっているかについての説明はコメントを参照してください):

IL_0001:  ldarg.0 // Push a on the stack
IL_0002:  ldarg.1 // Push b on the stack
IL_0003:  ldarg.2 // Push c on the stack
IL_0004:  ldarg.3 // Push d on the stack
IL_0005:  add     // Add d+c, push the result
IL_0006:  mul     // Multiply (d+c) by b
IL_0007:  add     // Add b*(d+c)+a

ご覧のとおり、オペランドは、式の後ろから前に作業することで操作を実行しやすくする順序でスタックにプッシュされます。これは、記事で説明されているとおりです。

変換の正確なアルゴリズムはコンパイラに依存します (厳密に言えば、式を有効な RPN シーケンスに変換する方法は複数あるため、最終結果もコンパイラに依存します) が、RPN の基本的な考え方はそこにあります。

于 2012-09-22T00:53:04.967 に答える