基本情報技術者 2014年 秋期 午前（科目A） 問05

加減乗除を組み合わせた計算式の処理において、スタックを利用するのが適している処理はどれか。【午前2 解説】

要点まとめ

• 結論：スタックは途中結果を一時的に積み上げ、別の計算を行った後で直近に格納した結果を取り出して結合する処理に最も適しています。
• 根拠：スタックはLIFO（最後に入れたものを先に取り出す）構造で、括弧や入れ子を伴う式の評価や中間計算のネストを自然に表現できます。
• 差がつくポイント：順序通りに取り出すFIFOやリストの中間挿入・昇順維持を要する処理とは用途が異なるため、問題文の「別の計算を行った後で結合する」に着目すると確実に選べます。

正解の理由

よくある誤解

• 「格納された順番に取り出す」がスタックの説明だと勘違いする：格納した順に取り出す＝FIFO（キュー）を想定する表現であり、スタックは逆順（LIFO）です。
• スタックでリストの中間要素を直接変更・挿入できると思い込む：スタックは末端（トップ）以外の挿入・変更が得意ではなく、直接の中間操作には不向きです。
• 「スタック＝常に高速で万能」と誤認：用途により適切な構造（キュー、配列、連結リスト、木など）を選ぶ必要があります。

解法ステップ

1. 問題文から「別の計算を行った後で結合する」などのキーワードがあるか注目する。
2. 「一時的に保存して後で取り出す」処理が存在すればLIFO（スタック）かFIFO（キュー）かを判定する。
3. 「直近に格納したものを優先して取り出す」という性質が明示または暗示されていればスタックを選択する。
4. 中間挿入や昇順維持などが要求されている選択肢はスタック以外を選ぶ。
5. 各選択肢を上記基準で当てはめ、最も用途が一致するものを正解とする。

選択肢別の誤答解説

• ア: 「格納された順番に取り出す処理」→ 格納順そのまま取り出すのはFIFO（キュー）に相当します。スタックは逆順で取り出すため不適切です。
• イ: 正解。途中結果をスタックに積んでおき、別の計算後に取り出して結合する操作は典型的なLIFO利用例です。
• ウ: 「昇順に並べられた途中結果のうち中間を変更する」→ ソート済みデータの中間更新やランダムアクセスが必要で、スタックは不適。配列や平衡二分木が適します。
• エ: 「リストの中間に途中結果を挿入する」→ 中間挿入は連結リストや配列で行う操作で、スタックは末端（トップ）以外への挿入に向きません。

補足コラム

• スタックの代表的用途：逆ポーランド記法（RPN）による式評価、シャントンヤード（shunting-yard）アルゴリズムでの演算子管理、関数呼び出しのコールスタック、DFS（深さ優先探索）の実装、Undo機能など。
• 中置式をポストフィックス（RPN）に変換して評価する例：中置式 $3+4\times 2$ は RPN で $342\times +$ となり、スタックで順に処理すれば簡単に評価できます。
• 簡単なRPN評価のPython例（スタック利用）：

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in ('+', '-', '*', '/'):
            b = stack.pop()
            a = stack.pop()
            if t == '+':
                stack.append(a + b)
            elif t == '-':
                stack.append(a - b)
            elif t == '*':
                stack.append(a * b)
            else:
                stack.append(a / b)
        else:
            stack.append(float(t))
    return stack.pop()

# 例: 3 4 2 * +
print(eval_rpn(["3", "4", "2", "*", "+"]))  # 出力 11.0

FAQ

• Q: スタックとキューの違いは？
  A: スタックはLIFO（最後に入れたものを最初に取り出す）、キューはFIFO（最初に入れたものを最初に取り出す）です。用途が異なるため混同しないことが重要です。
• Q: 括弧を含む式評価ではなぜスタックが使われる？
  A: 括弧は入れ子構造を作るため、内側の計算結果を一時保存しておき、外側で取り出して使用するというLIFOの流れが自然に対応します。
• Q: スタックで中間挿入は可能ですか？
  A: 実装上は可能でも効率的ではなく、スタックの本来の用途ではありません。中間挿入が多いなら別のデータ構造を選ぶべきです。
• Q: スタックの時間計算量は？
  A: push/pop は通常O(1)です。式全体の評価はトークン数に比例してO(n)になります。