中置記法とは何ですか?
中置記法は、式を通常の形式または通常の形式で記述する記法です。演算子がオペランドの間にある表記法です。中置記法の例としては、A+B、A*B、A/B などがあります。
上記の例でわかるように、すべての演算子はオペランドの間に存在するため、中置表記となります。したがって、中置記法の構文は次のように記述できます。
中置式の解析
式を解析するには、次の 2 つのことに注意する必要があります。 演算子の優先順位 そして 結合性 。演算子の優先順位とは、他の演算子に対する演算子の優先順位を意味します。例えば：
A + B * C → A + (B * C)
乗算演算子は加算演算子よりも優先されるため、B * C 式が最初に評価されます。 B * C の乗算の結果が A に加算されます。
優先順位
| オペレーター | 記号 |
|---|---|
| 括弧 | { }、( )、[ ] |
| 指数表記 | ^ |
| 掛け算と割り算 | *、/ |
| 加減 | +、- |
結合性とは、同じ優先順位を持つ演算子が式内に存在する場合を意味します。たとえば、式 (A + B - C) では、「+」演算子と「-」演算子は同じ優先順位を持っているため、結合性を利用して評価されます。 「+」と「-」は両方とも左結合であるため、(A + B) - C として評価されます。
次のJavaスキャナー
結合順序
| オペレーター | 結合性 |
|---|---|
| ^ | 右から左に |
| *、/ | 左から右へ |
| +、- | 左から右へ |
例を通して結合性を理解しましょう。
1 + 2*3 + 30/5
上記の式では * と / の優先順位が同じであるため、結合規則を適用します。上の表でわかるように、* 演算子と / 演算子には左から右への結合性があるため、左端の演算子からスキャンします。最初にある演算子が最初に評価されます。演算子 * は / 演算子の前に表示され、乗算が最初に実行されます。
1+(2*3)+(30/5)
ラテックスマトリックス
1+6+6 = 13
接頭辞表記とは何ですか?
接頭辞表記は別の表現形式ですが、優先順位や結合性などの他の情報を必要としません。一方、中置表記は優先順位や結合性の情報を必要とします。としても知られています ポーランド語表記 。接頭辞表記では、演算子はオペランドの前に来ます。接頭辞表記の構文は次のとおりです。
例えば、 中置式が 5+1 の場合、この中置式に対応する接頭式は +51 になります。
中置式が次の場合:
a * b + c
↓
*ab+c
↓
+*abc (プレフィックス式)
別の例を考えてみましょう。
A + B * C
最初のスキャン： 上の式では、乗算演算子は加算演算子よりも優先されます。 B*C の接頭辞表記は (*BC) になります。
A + *BC
2 回目のスキャン: 2 回目のスキャンでは、プレフィックスは次のようになります。
Pythonの継承プログラム
+A *BC
上記の式では、2 回のスキャンを使用して中置式を前置式に変換します。式が複雑な場合、より多くのスキャンが必要になります。 1 回のスキャンだけで必要な結果が得られるこの方法を使用する必要があります。 1 回のスキャンで目的の出力が得られる場合、アルゴリズムは効率的になります。これはスタックを使用する場合にのみ可能です。
スタックを使用したインフィックスからプレフィックスへの変換
K + L - M * N + (O^P) * W/U/V * T + Q
式を中置文字から接頭辞に変換する場合は、まず式を逆にする必要があります。
逆の式は次のようになります。
Q + T * V/U/W * ) P^O(+ N*M - L + K
gimp用のフォント
プレフィックス式を取得するために、入力式、スタック、プレフィックス式の 3 つの列で構成されるテーブルを作成しました。シンボルに遭遇したら、それを接頭辞式に追加するだけです。演算子が見つかった場合は、それをスタックにプッシュします。
| 入力式 | スタック | 接頭辞式 |
|---|---|---|
| Q | Q | |
| + | + | Q |
| T | + | QT |
| * | +* | QT |
| で | +* | QTV |
| / | +*/ | QTV |
| で | +*/ | QTVU |
| / | +*// | QTVU |
| で | +*// | QTVUW |
| * | +*//* | QTVUW |
| ) | +*//*) | QTVUW |
| P | +*//*) | QTVUWP |
| ^ | +*//*)^ | QTVUWP |
| ○ | +*//*)^ | QTVUWPO |
| ( | +*//* | QTVUWPO^ |
| + | ++ | QTVUWPO^*//* |
| N | ++ | QTVUWPO^*//*N |
| * | ++* | QTVUWPO^*//*N |
| M | ++* | QTVUWPO^*//*NM |
| - | ++- | QTVUWPO^*//*NM* |
| L | ++- | QTVUWPO^*//*NM*L |
| + | +-+ | QTVUWPO^*//*NM*L |
| K | +-+ | QTVUWPO^*//*NM*LK |
| QTVUWPO^*//*NM*LK+-++ |
上記の式、つまり QTVUWPO^*//*NM*LK+-++ は最終的な式ではありません。プレフィックス式を取得するには、この式を逆にする必要があります。
インフィックスからプレフィックス式への変換のルール:
- まず、問題に示されている中置式を逆にします。
- 式を左から右にスキャンします。
- オペランドが到着するたびに、それらを出力します。
- オペレーターが到着し、スタックが空であることが判明した場合は、単純にオペレーターをスタックにプッシュします。
- 受信演算子の優先順位がスタックの TOP よりも高い場合は、受信演算子をスタックにプッシュします。
- 受信演算子がスタックの TOP と同じ優先順位を持っている場合は、受信演算子をスタックにプッシュします。
- 受信演算子の優先順位がスタックの先頭よりも低い場合は、スタックの先頭をポップして出力します。受信した演算子をスタックの最上位に対して再度テストし、より低い優先順位または同じ優先順位の演算子が見つかるまでスタックから演算子をポップします。
- 受信演算子がスタックの先頭と同じ優先順位を持ち、受信演算子が ^ の場合、条件が true になるまでスタックの先頭をポップします。条件が true でない場合は、^ 演算子をプッシュします。
- 式の終わりに到達したら、スタックの一番上からすべての演算子をポップして出力します。
- 演算子が「)」の場合は、それをスタックにプッシュします。
- 演算子が '(' の場合、スタック内で左括弧 ) が見つかるまで、すべての演算子をスタックからポップします。
- スタックの最上位が ')' の場合、演算子をスタックにプッシュします。
- 最後に出力を反転します。
インフィックスからプレフィックスへの変換の擬似コード
Function InfixtoPrefix( stack, infix) infix = reverse(infix) loop i = 0 to infix.length if infix[i] is operand → prefix+= infix[i] else if infix[i] is '(' → stack.push(infix[i]) else if infix[i] is ')' → pop and print the values of stack till the symbol ')' is not found else if infix[i] is an operator(+, -, *, /, ^) → if the stack is empty then push infix[i] on the top of the stack. Else → If precedence(infix[i] > precedence(stack.top)) → Push infix[i] on the top of the stack else if(infix[i] == precedence(stack.top) && infix[i] == '^') → Pop and print the top values of the stack till the condition is true → Push infix[i] into the stack else if(infix[i] == precedence(stack.top)) → Push infix[i] on to the stack Else if(infix[i] <precedence(stack.top)) → pop the stack values and print them till is not empty infix[i] < precedence(stack.top) push on to end loop remaining elements of prefix="reverse(prefix)" return pre> <hr></precedence(stack.top))>