データ構造 - 式解析

式解析（Parsing Expressions）は、スタックというデータ構造の最も古典的な適用例です。

式解析では、スタックを利用して中置・前置・後置式間の変換と式の評価を行う方法を示します。

3 種類の式表現

中置式 A + B * C を後置式に変換 — 手順のデモ
ステップ 1A を読むオペランドなので、そのまま出力出力: Aスタック: 空
ステップ 2+ を読む演算子なので、スタックにプッシュ出力: Aスタック: +
ステップ 3B を読むオペランドなので、そのまま出力出力: ABスタック: +
ステップ 4* を読む* の優先順位 > + なので、スタックにプッシュ出力: ABスタック: +*
ステップ 5C を読むオペランドなので、そのまま出力出力: ABCスタック: +*
ステップ 6終了スタック内のすべての演算子をポップ出力: ABC*+スタック: 空
最終結果: A + B * C → A B C * +

コンピュータで数式を処理する際、表現方法は 3 つあります。

種類演算子の位置例評価の難しさ括弧の必要性
中置式オペランドの間（人間向き）A + B * C優先順位と括弧の処理が必要必要
前置式（ポーランド記法）オペランドの前+ A * B C1 回走査するだけ不要
後置式（逆ポーランド記法）オペランドの後A B C * +1 回走査するだけ不要

後置式と前置式の最大の利点は、評価中に演算子の優先順位や括弧をまったく考慮する必要がなく、左から右へ順番に走査するだけで済むことです。

中置記法から後置記法への変換アルゴリズム（Shunting Yard アルゴリズムの考え方）

中置式を後置式に変換する中核アルゴリズムはスタックを用いて実現します。基本的な流れは以下の通りです。

  1. 中置式を左から右へ走査する
  2. 場合オペランド（数字/文字）なら、そのまま出力
  3. 場合演算子、それをスタックトップの演算子と優先順位を比較します：
    • スタックトップの演算子の優先順位がより高いか等しい場合は、スタックトップをポップして出力します
    • 現在の演算子をスタックにプッシュできるようになるまでこの処理を繰り返します
  4. 場合左括弧、そのままスタックにプッシュ
  5. 場合右括弧、左括弧に遭遇するまでスタックトップの演算子をポップして出力し続けます（左括弧自体はポップしますが出力しません）
  6. 走査が終了したら、スタックに残っている演算子を順番にポップして出力します

例

#include <stdio.h>
#include <ctype.h> /* isalnum 関数 */
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) { stack[++top] = c; }
char pop() { return (top == -1) ? -1 : stack[top--]; }

/* 演算子の優先順位を返す：数値が大きいほど優先順位が高い */
int precedence(char op) {
    if (op == '+' || op == '-') return 1;  /* 加減算は優先順位が最も低い */
    if (op == '*' || op == '/') return 2;  /* 乗除算は優先順位が高い */
    if (op == '^') return 3;               /* べき乗は優先順位が最優先 */
    return 0;  /* 演算子ではない */
}

/* 中置式を後置式に変換
引数：infix 入力の中置式文字列
postfix 出力用の後置式バッファ */
void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    char c;

    while ((c = infix[i++]) != '\0') {
        /* オペランド（文字または数字）：そのまま出力 */
        if (isalnum(c)) {
            postfix[j++] = c;
        }
        /* 左括弧：そのままスタックにプッシュ */
        else if (c == '(') {
            push(c);
        }
        /* 右括弧：左括弧に遭遇するまでポップ */
        else if (c == ')') {
            while (top != -1 && stack[top] != '(') {
                postfix[j++] = pop();
            }
            pop();  /* 左括弧 '(' をポップするが、出力しない */
        }
        /* 演算子：優先順位を処理 */
        else {
            while (top != -1 &&
                   precedence(stack[top]) >= precedence(c) &&
                   stack[top] != '(') {
                postfix[j++] = pop();
            }
            push(c);
        }
    }

    /* スタックに残っている演算子をすべてポップ */
    while (top != -1) {
        postfix[j++] = pop();
    }
    postfix[j] = '\0';  /* 文字列の末尾 */
}

int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];

    infixToPostfix(infix, postfix);
    printf("中置: %s\n", infix);      /* 出力: 中置: A+B*C */
    printf("後置: %s\n", postfix);    /* 出力: 後置: ABC*+ */
    return 0;
}

後置式の評価

後置式 5 3 + 2 * の評価 — 手順のデモ
ステップ 15 を読む数字なので、スタックにプッシュスタック: 5
ステップ 23 を読む数字なので、スタックにプッシュスタック: 5 3
ステップ 3+ を読む3 と 5 をポップし、5+3=8 を計算して結果をスタックにプッシュスタック: 85+3=8
ステップ 42 を読む数字なので、スタックにプッシュスタック: 8 2
ステップ 5* を読む2 と 8 をポップし、8*2=16 を計算して結果をスタックにプッシュスタック: 168*2=16
結果終了スタックには 16 だけが残り、それが計算結果です結果 = 16
後置 53+2* = 16（中置 (5+3)*2 と同等）

後置式があれば、スタックを使った評価は非常に直接的です。オペランドに遭遇したらスタックにプッシュし、演算子に遭遇したら2つのオペランドをポップして計算し、再びプッシュします。

例

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

#define MAX 100

int stack[MAX];
int top = -1;

void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }

/* 後置式の値を計算する
引数：postfix 後置式（オペランドはすべて単一の数字 0-9）
戻り値：式の計算結果 */
int evaluatePostfix(char* postfix) {
    int i = 0;
    char c;

    while ((c = postfix[i++]) != '\0') {
        /* オペランド：数字に変換してスタックにプッシュ */
        if (isdigit(c)) {
            push(c - '0');  /* '3' を整数 3 に変換 */
        }
        /* 演算子：2つのオペランドをポップし、計算してからプッシュし直します */
        else {
            int b = pop();  /* 2番目のオペランド（右オペランド） */
            int a = pop();  /* 1番目のオペランド（左オペランド） */
            switch (c) {
                case '+': push(a + b); break;
                case '-': push(a - b); break;
                case '*': push(a * b); break;
                case '/': push(a / b); break;
            }
        }
    }
    return pop();  /* スタックの最後の要素が最終結果 */
}

int main() {
    /* 後置式 "23+5*" は中置 "(2+3)*5" = 25 と同等 */
    char postfix[] = "23+5*";
    int result = evaluatePostfix(postfix);
    printf("後置 %s = %d\n", postfix, result);  /* 出力: 後置 23+5* = 25 */
    return 0;
}

後置式を評価するとき、オペランドのポップ順序が非常に重要です。最初にポップされるのは右オペランド（b）、次にポップされるのは左オペランド（a）です。これは減法や除法などの非対称な演算では特に重要で、順序を間違えると結果が誤ります。

完全な例：中置記法の評価

上記の 2 つの手順を組み合わせることで、完全な電卓を実現できます：中置 → 後置 → 評価。

例

#include <stdio.h>
#include <ctype.h>

#define MAX 100

/* 演算子の優先順位を扱う補助関数（同上）、評価関数（同上）、変換関数（同上） */
/* 簡潔にするため、上記で定義した関数は省略しています。実際に使用する際はこれらの関数を含める必要があります */

int main() {
    char infix[] = "5+3*2";            /* 中置式 */
    char postfix[MAX];
    infixToPostfix(infix, postfix);    /* ステップ 1：後置に変換 */

    printf("中置: %s\n", infix);       /* 出力: 中置: 5+3*2 */
    printf("後置: %s\n", postfix);     /* 出力: 後置: 532*+ */

    int result = evaluatePostfix(postfix);  /* ステップ 2：評価 */
    printf("結果: %s = %d\n", infix, result);
    /* 出力: 結果: 5+3*2 = 11 */
    return 0;
}
その他の拡張