データ構造-式の解析

算術式を書く方法は、 notation。算術式は、式の本質や出力を変更せずに、3つの異なるが同等の表記法で記述できます。これらの表記は-

中置記法
プレフィックス（ポーランド語）表記
後置（逆ポーランド）表記

これらの表記は、式で演算子を使用する方法として名前が付けられています。この章でも同じことを学びます。

中置記法

式を書く infix 表記、たとえばa --b + c、ここで演算子が使用されます in-オペランド間。私たち人間は中置記法で読み、書き、話すのは簡単ですが、同じことはコンピューティングデバイスではうまくいきません。中置記法を処理するアルゴリズムは、時間とスペースの消費の点で困難でコストがかかる可能性があります。

プレフィックス表記

この表記では、演算子は prefixオペランドに編集されます。つまり、演算子はオペランドの前に書き込まれます。例えば、+ab。これは、中置記法と同等ですa + b。プレフィックス表記は、Polish Notation。

後置表記

この記譜スタイルは、 Reversed Polish Notation。この記譜法では、演算子はpostfixオペランドに編集されます。つまり、演算子はオペランドの後に記述されます。例えば、ab+。これは、中置記法と同等ですa + b。

次の表は、3つの表記すべての違いを簡単に示しています。

シニア番号	中置記法	プレフィックス表記	後置表記
1	a + b	+ ab	ab +
2	（a + b）∗ c	∗ + abc	ab + c ∗
3	a ∗（b + c）	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	（a + b）∗（c + d）	∗ + ab + cd	ab + cd + ∗
6	（（a + b）∗ c）-d	-∗ + abcd	ab + c ∗ d-

式の解析

すでに説明したように、中置記法を解析するアルゴリズムやプログラムを設計するのはあまり効率的な方法ではありません。代わりに、これらの中置記法は最初に接尾辞または接頭辞表記のいずれかに変換されてから計算されます。

算術式を解析するには、演算子の優先順位と結合性にも注意を払う必要があります。

優先順位

オペランドが2つの異なる演算子の間にある場合、どちらの演算子が最初にオペランドを取得するかは、他の演算子に対する演算子の優先順位によって決定されます。例-

乗算演算は加算よりも優先されるため、b * cが最初に評価されます。演算子の優先順位の表は後で提供されます。

結合性

結合性は、同じ優先順位を持つ演算子が式に現れる規則を表します。たとえば、式a + b − cでは、+と–の両方が同じ優先順位を持ち、式のどの部分が最初に評価されるかは、これらの演算子の結合性によって決定されます。ここでは、+と-の両方が結合性のままであるため、式は次のように評価されます。(a + b) − c。

優先順位と結合性は、式の評価の順序を決定します。以下は、演算子の優先順位と結合性の表（最高から最低）です。

シニア番号	オペレーター	優先順位	結合性
1	べき乗^	最高	右結合性
2	掛け算（∗）＆割り算（/）	2番目に高い	左結合
3	足し算（+）＆引き算（−）	最低	左結合

上記の表は、演算子のデフォルトの動作を示しています。式の評価の任意の時点で、括弧を使用して順序を変更できます。例-

に a + b*c、表現部分 b*c最初に評価され、加算よりも乗算が優先されます。ここでは括弧を使用しますa + b 最初に評価されるように (a + b)*c。

接尾辞評価アルゴリズム

ここで、後置記法を評価する方法に関するアルゴリズムを見てみましょう。

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 operation

Cプログラミング言語での実装を確認するには、ここをクリックしてください。