5

数式は通常、中置記法で表されます。評価目的で、後置 (リバース ポリッシュ) 表記に変更し ( Shunting-Yardなどのアルゴリズムを使用)、スタックを使用して後置表記を評価できます。

計算機がこの手法を使用していることがわかりましたが、今日の最新のコンパイラはこれを算術式の評価に使用していますか? それは十分に効率的ですか、それとも他の手法 (またはアルゴリズム) が使用されていますか?

4

1 に答える 1

8

この質問に答えるために、あなたが言及した概念に焦点を当て、infix notationそれらShunting-Yardをevaluationコンパイルに関連付けましょう。

まず、コンピュータがどのように式を処理するかを理解する必要があります。式は、コードの作成に使用される抽象構文ツリー(AST) に変換されます。ツリーをコードに変換するプロセスはさまざまですが、AST のウォークは式の評価と同じです。

1+2 の AST:

   + 
  / \ 
 1   2

接尾辞:1 2 +

1これは、左の分岐を
調べ、右の分岐 を調べ2、演算子を 2 つのオペランドに
適用することによって評価されます。+

1*2+3^4 の AST:

     + 
   /   \
  ^     *
 / \   / \
3   4 1   2

接尾辞:3 4 ^ 1 2 * +

これは、左枝にアクセスし3^4、
次にその左枝にアクセスし3、
次にその右枝にアクセスし4、
次に演算子にアクセスして評価し^、それを評価3^4して `+' の新しい左枝として保持することによって評価されます。つまり、81

次に右枝にアクセスし1*2、
次に左枝にアクセスし1、次に
右枝にアクセスし2、
次に演算子にアクセスし、それ*を評価1*2して「+」の新しい右枝として保持します。つまり、2

次に、演算子を訪問し、それ+を評価81+2して結果として返します83

現在、中置記法は、人間が式を読みやすくするための構文糖衣です。infix-notation を AST に変換するのを助けるために、変換アルゴリズムは演算子の優先順位と結合性を知る必要があります。このアルゴリズムは、Shunting-Yard アルゴリズムの主要な鍵の 1 つであるスタックも使用します。インフィックスを評価戦略に変換するために私が知っているすべての手段は、何らかの方法でスタックを使用します。

コンパイラは、電卓アプリケーションで実行できるように式を明示的に評価しませんが、評価のためにツリーのウォーキングを評価を実行するコードに変換します。

注: 私はすべての言語のすべてのコンパイラを知っているわけではないので、一般的な概念に基づいた回答しかできません。これらに従うことを要求する規則はありません。一部のコンパイラが AST をスキップし、AST を使用せずに入力コードからコンパイル済みコードに移行しても驚かないでしょう。

また、コンパイラについて言及したので、コンパイルされたコードについてのみ話し、スクリプト言語には触れませんでした。

質問に戻ります。

今日の最新のコンパイラは、これを算術式の評価に使用していますか?

特に Shunting-Yard アルゴリズムを使用するのではなく、使用するアルゴリズムの重要な概念の 1 つであるスタックを使用するという概念を使用します。アルゴリズムの概念を使用することがアルゴリズムを使用することと同じである場合は、自分で選択できます。

それは十分に効率的ですか、それとも他の手法 (またはアルゴリズム) が使用されていますか?

うまくいけば、あなたはこの質問に対する答えを知っているでしょう。重要なのは Shunting-Yard アルゴリズムではなく、スタックを使用して infix-notation を変換するという概念が重要であり、コンパイラで使用されるものです。コンパイルされた言語は通常、式を評価するだけでなく、型を操作し、条件式を処理し、値を格納し、メソッド/関数、クラス、モジュールなどの上位の型を作成することを覚えておいてください。

于 2013-12-26T13:31:21.567 に答える