C言語で学ぶスタックによる式の変換：中置記法から後置・前置記法への変換アルゴリズム

スタック（Stack）とは、データの挿入と削除が同じ一端のみで行われる線形データ構造です。この性質を「LIFO（Last In First Out：後入れ先出し）」と呼びます。

スタックの基本操作とアルゴリズム

Push（プッシュ）のアルゴリズム

まず、スタックオーバーフローが発生していないかを確認します。

if (top == n-1)
    printf("stack over flow");

オーバーフローでなければ、要素をスタックに挿入します。

top++;
a[top] = item;

Pop（ポップ）のアルゴリズム

まず、スタックアンダーフローが発生していないかを確認します。

if (top == -1)
    printf("stack under flow");

アンダーフローでなければ、スタックから要素を取り出します。

item = a[top];
top--;

Display（表示）のアルゴリズム

スタックが空かどうかを判定します。

if (top == -1)
    printf("stack is empty");

空でなければ、以下の手順でスタックの中身を表示します。

for (i = 0; i < top; i++)
    printf("%d", a[i]);

スタックの応用：式の変換

スタックはC言語における式の変換にも活用されます。ここでは、その仕組みを詳しく見ていきましょう。

式とは

式（Expression）とは、演算対象（オペランド）と演算子（オペレータ）を合法的に組み合わせたものです。

式の種類

C言語では、変換や評価の対象となる式として次の3種類があります。

• 中置記法（Infix）：演算子がオペランドの間に置かれる形式。例：A+B
• 前置記法（Prefix）：演算子がオペランドの前に置かれる形式。例：+AB
• 後置記法（Postfix）：演算子がオペランドの後に置かれる形式。例：AB+

変換の基本例

中置記法から後置記法・前置記法への基本的な変換例は以下の通りです。

【中置 → 後置】        【中置 → 前置】
A + B*C                A + B*C
A + BC*                A + *BC
ABC*+                  +A*BC

具体的な変換例

例として、A+B*C/D-E+F を後置記法と前置記法に変換してみましょう。

【中置 → 前置】              【中置 → 後置】
A +B*C / D-E+F               A +B*C / D-E+F
A +*BC / D-E+F               A +BC* / D-E+F
A +/*BCD -E+F                A +BC*D/-E+F
+A/*BCD -E+F                 ABC*D/+ -E+F
-+A/*BCDE +F                 ABC*D/+E- +F
+-+A/*BCDEF                  ABC*D/+E-F+

中置記法から後置記法への変換アルゴリズム

入力文字列を左から右へ走査しながら、以下の手順に従って処理を行います。

1. ステップ1：入力記号がオペランド（被演算子）の場合、画面に出力します。
2. ステップ2：入力記号が「(」（開き括弧）の場合、スタックにプッシュします。
3. ステップ3：入力記号が「)」（閉じ括弧）の場合、「(」が出てくるまでスタックの内容をすべてポップします。
4. ステップ4：入力記号が演算子の場合、スタックの最上位にある演算子と現在の入力記号の優先順位を比較します。
   • スタック最上位の優先順位が現在の記号以上であれば、スタックの内容をポップし、現在の記号をスタックにプッシュします。
   • そうでなければ、単純に演算子をスタックにプッシュします。
5. ステップ5：入力記号が「\0」（文字列の終端）の場合、スタックが空になるまで内容をすべてポップします。

変換処理の流れ

スタックを用いた中置記法から後置記法への実際の変換過程は、下図のように段階的に進みます。