中置記法から後置記法への変換を理解する前に、中置記法と後置記法について別々に知っておく必要があります。

中置子と後置子は式です。式は定数、変数、シンボルで構成されます。記号には演算子または括弧を使用できます。これらすべての式を一連のルールを使用して評価できるように、これらすべてのコンポーネントを一連のルールに従って配置する必要があります。

式の例は次のとおりです。

5+6

A～B

配列リストのソート

(P*5)

上記の式はすべて共通の構造を持っています。つまり、2 つのオペランドの間に演算子があります。オペランドは、操作が実行されるオブジェクトまたは値です。上記の式では、5、6 がオペランド、「+」、「-」、および「*」が演算子です。

中置記法とは何ですか?

演算子がオペランドの間に記述される場合、それは次のように呼ばれます。 中置記法 。オペランドは必ずしも定数または変数である必要はありません。式自体にすることもできます。

例えば、

(p + q) * (r + s)

上の式では、乗算演算子の両方の式がオペランドです。つまり、 (p + q) 、 そして (r + s) はオペランドです。

上の式には 3 つの演算子があります。最初のプラス演算子のオペランドは p と q で、2 番目のプラス演算子のオペランドは r と s です。を実行しながら、 式に対する操作では、結果を評価するためにいくつかのルールに従う必要があります。の中に 上の式では、2 つの式、つまり p+q と r+s に対して加算演算が実行され、次に乗算演算が実行されます。

中置記法の構文は次のとおりです。

式に演算子が 1 つだけある場合は、ルールを適用する必要はありません。たとえば、5 + 2;この式では、2 つのオペランド (5 と 2) の間で加算演算を実行でき、演算結果は 7 になります。

式に複数の演算子がある場合、式を評価するには何らかのルールに従う必要があります。

式が次の場合:

電子バンキングの制限

4+6*2

プラス演算子が最初に評価される場合、式は次のようになります。

10 * 2 = 20

乗算演算子が最初に評価される場合、式は次のようになります。

DSにスタックする

4 + 12 = 16

上記の問題は、演算子の優先順位規則に従うことで解決できます。代数式における演算子の優先順位は、次の表に示されています。

最初に優先されるのは括弧です。次に指数が優先されます。複数の指数演算子の場合、演算は右から左に適用されます。

例えば：

2^2^3 = 2^8

= 256

指数、乗算、除算の演算子が評価された後。両方の演算子が式に存在する場合、演算は左から右に適用されます。

次に優先されるのは加算と減算です。両方の演算子が式で使用できる場合は、左から右に進みます。

同じ優先順位を持つ演算子は、 演算子の結合性 。左から右に進む場合、それは左連想として知られています。右から左に進む場合、それは右連想として知られています。

中置記法の問題

中置式を評価するには、次のことについて知っておく必要があります。 演算子の優先順位 ルールに従う必要があり、演算子の優先順位が同じである場合は、次の規則に従う必要があります。 結合性 ルール。中置記法では、演算の実行順序を制御するために括弧の使用が非常に重要です。括弧を使用すると式が読みやすくなります。中置式は式を記述する最も一般的な方法ですが、曖昧さなしに中置式を解析して評価するのは簡単ではありません。そこで、数学者と論理学者はこの問題を研究し、式を記述する別の 2 つの方法、つまり接頭辞と接尾辞を発見しました。どちらの式も括弧を必要とせず、曖昧さなく解析できます。演算子の優先順位や結合規則は必要ありません。

後置式

後置式は、オペランドの後に演算子を記述する式です。たとえば、中置記法の後置式 ( 2+3) は 23+ と書くことができます。

リストから配列Javaへ

後置式に関する重要なポイントは次のとおりです。

• 後置式では、左から右に書いた順に演算が行われます。
• 括弧は必要ありません。
• 演算子の優先順位ルールや結合性ルールを適用する必要はありません。

後置式を評価するアルゴリズム

• 演算子が見つかるまで、式を左から右にスキャンします。
• 操作を実行する
• 式を計算された値に置き換えます。
• 演算子がなくなるまで 1 から 3 の手順を繰り返します。

例を通して上記のアルゴリズムを理解してみましょう。

中置式: 2 + 3 * 4

式の左端からスキャンを開始します。乗算演算子は、左から右にスキャンするときに最初に現れる演算子です。ここで、式は次のようになります。

式 = 2 + 34*

= 2 + 12

もう一度、左から右にスキャンすると、式は次のようになります。

式 = 2 12 +

= 14

スタックを使用した後置式の評価。

• 式を左から右にスキャンします。
• 式内でオペランドが見つかった場合は、そのオペランドをスタックにプッシュします。
• 式内で演算子が見つかった場合は、対応するオペランドをスタックからポップします。
• 式のスキャンが終了すると、最終的な値がスタックに残ります。

スタックを使用した後置式の評価を理解しましょう。

例 1: 後置式: 2 3 4 * +

上記の式の結果は 14 になります。

例 2: 後置式: 3 4 * 2 5 * +

上記の式の結果は 22 です。

c ブール値

後置式を評価するアルゴリズム

1. 文字を読む
2. 文字が数字の場合は、文字を int に変換し、整数をスタックにプッシュします。
3. キャラクターが演算子の場合、
   • スタックから要素を 2 回ポップし、2 つのオペランドを取得します。
   • 操作を実行する
   • 結果をスタックにプッシュします。

インフィックスからポストフィックスへの変換

ここでは、中置式から前置式への変換にスタック データ構造を使用します。オペレーターが遭遇するたびに、オペレーターをスタックにプッシュします。オペランドが見つかった場合は、そのオペランドを式に追加します。

中置式から後置式への変換の規則

1. オペランドが到着したらそれを出力します。
2. スタックが空であるか、上部に左括弧が含まれている場合は、受信した演算子をスタックにプッシュします。
3. 受信シンボルが '(' の場合、それをスタックにプッシュします。
4. 受信シンボルが ')' の場合、スタックをポップし、左括弧が見つかるまで演算子を出力します。
5. 受信シンボルの優先順位がスタックの最上位よりも高い場合は、それをスタックにプッシュします。
6. 受信シンボルの優先順位がスタックの最上位よりも低い場合は、スタックの最上位をポップして出力します。次に、受信した演算子をスタックの新しい最上位に対してテストします。
7. 入力演算子がスタックの最上位と同じ優先順位を持つ場合は、結合規則を使用します。結合性が左から右の場合は、スタックの一番上をポップおよび出力してから、入力された演算子をプッシュします。結合性が右から左の場合は、入力された演算子をプッシュします。
8. 式の最後で、スタックのすべての演算子をポップして出力します。

例を通して理解しましょう。

中置式: K + L - M*N + (O^P) * W/U/V * T + Q

中置式(K + L - M*N + (O^P) * W/U/V * T + Q) の最後の後置式は、KL+MN*-OP^W*U/V/T*+Q+ です。 。