Data-structures-algorithms-expression-parsing
データ構造-式の解析
算術式を記述する方法は、*表記法*と呼ばれます。 算術式は、3つの異なるが同等の表記法で、つまり式の本質や出力を変更せずに記述できます。 これらの表記法は-
- 中置記法
- プレフィックス（ポーランド語）表記
- 後置（逆ポーランド）表記
これらの表記は、式で演算子を使用する方法として名前が付けられています。 この章でも同じことを学びます。
中置記法
式を infix 表記で記述します。 a-b＆plus; c、オペランド間で演算子が使用されます。 私たち人間は中置記法で読み、書き、話すことは簡単ですが、同じことがコンピューティングデバイスにはうまくいきません。 中置記法を処理するアルゴリズムは、時間とスペースの消費の観点から困難でコストがかかる可能性があります。
プレフィックス表記
この表記では、演算子はオペランドに接頭辞が付けられています。 演算子はオペランドの前に記述されます。 たとえば、＆plus; ab *。 これは、中置表記 *a＆plus;と同じです。 b 。 プレフィックス表記は、*ポーランド表記*とも呼ばれます。
後置記法
この表記スタイルは*逆ポーランド表記*として知られています。 この表記スタイルでは、演算子はオペランドに後置されます。つまり、演算子はオペランドの後に記述されます。 たとえば、 ab＆plus; 。 これは、中置表記 a＆plus;と同じです。 b 。
次の表では、3つの表記すべての違いを簡単に示します-
| Sr.No. | Infix Notation | Prefix Notation | Postfix Notation |
|---|---|---|---|
| 1 | a PLUS b | PLUS a b | a b PLUS |
| 2 | (a PLUS b) ∗ c | ∗ PLUS a b c | a b PLUS c ∗ |
| 3 | a ∗ (b PLUS c) | ∗ a PLUS b c | a b c PLUS ∗ |
| 4 | a/b PLUS c/d | PLUS/a b/c d | a b/c d/PLUS |
| 5 | (a PLUS b) ∗ (c PLUS d) | ∗ PLUS a b PLUS c d | a b PLUS c d PLUS ∗ |
| 6 | ((a PLUS b) ∗ c) - d | - ∗ PLUS a b c d | a b PLUS c ∗ d - |
式の解析
すでに説明したように、中置表記法を解析するためのアルゴリズムまたはプログラムを設計するのは非常に効率的な方法ではありません。 代わりに、これらのインフィックス表記法は、最初にポストフィックスまたはプレフィックス表記法に変換されてから計算されます。
算術式を解析するには、演算子の優先順位と結合性にも注意する必要があります。
優先順位
オペランドが2つの異なる演算子の間にある場合、どちらの演算子が最初にオペランドを取るかは、演算子の優先順位によって決定されます。 たとえば-
乗算演算は加算よりも優先されるため、b * cが最初に評価されます。 演算子の優先順位の表は後で提供されます。
連想性
結合性は、同じ優先順位を持つ演算子が式に現れるルールを記述します。 たとえば、式で＆plus; b-c、両方＆plus;および–同じ優先順位を持ち、式のどの部分が最初に評価されるかは、それらの演算子の結合性によって決まります。 ここでは、両方の＆plus;および-は連想式のままなので、式は*（a＆plus; b）-c *として評価されます。
優先順位と結合性は、式の評価の順序を決定します。 以下は、演算子の優先順位と結合性テーブル（最高から最低）です-
| Sr.No. | Operator | Precedence | Associativity |
|---|---|---|---|
| 1 | Exponentiation ^ | Highest | Right Associative |
| 2 | Multiplication ( ∗ ) & Division (/) | Second Highest | Left Associative |
| 3 | Addition ( PLUS ) & Subtraction ( − ) | Lowest | Left Associative |
上記の表は、演算子のデフォルトの動作を示しています。 式評価の任意の時点で、括弧を使用して順序を変更できます。 たとえば-
*a＆plus; b* c *、式部分 *b* * *c* が最初に評価され、乗算が加算よりも優先されます。 ここでは、 *a＆plus;に括弧を使用します。* （a＆plus; b） *c* のように、最初に評価されるb *。後置評価アルゴリズム
ここで、後置記法の評価方法に関するアルゴリズムを見てみましょう-
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operationCプログラミング言語での実装を確認するには、リンク：/data_structures_algorithms/expression_parsing_using_statck [ここをクリック]をクリックしてください。
