応用情報技術者 2011年 春期 午前2 問07

スタック逆追跡【午前2解説】

正解の理由

• 命令は合計で PUSH 7 回、POP 3 回なので純増は +4。最終スタックの要素数 5 から逆算すると初期スタックには 1 要素存在したことが分かる（$5-(7-3)=1$）。
• 最終状態から命令を逆順に「取り消す（PUSH の取り消し＝POP、POP の取り消し＝PUSH））」ことで各 PUSH が実際に積んだ値を特定できる。逆順で取り消したとき、1 番目の PUSH に対応する取り消しで得られる値は 7 である。

解法ステップ

1. 命令列を位置番号付きで整理（前→後）： 1:PUSH、2:PUSH、3:POP、4:PUSH、5:PUSH、6:PUSH、7:PUSH、8:POP、9:POP、10:PUSH （PUSH 合計 7 回、POP 合計 3 回）
2. 終状態のスタック（上→下）を S = [192, 55, 326, 7, 29] とする。要素数は 5。
3. ネットでの増減は PUSH−POP = 7−3 = 4。従って初期スタックの要素数は 5−4 = 1。初期スタックには 1 要素（未知値）がある。
4. 命令を逆順（10→1）に辿り、各命令を取り消す：
   • 取り消しルール： forward の PUSH の取り消し = POP（スタックから値を取り出す）／ forward の POP の取り消し = PUSH（取り出された値をスタックに戻す、値は不明ならプレースホルダ）
5. 実際の逆追跡（主要ステップのみ）：
   • 逆に 10 番命令（元は PUSH）：スタックの最上位 192 を取り除く → これが P7 の値（P7 = 192）。残り [55,326,7,29]。
   • 9 番（元 POP）の取り消し：不明値 Y9 をスタックに戻す → [Y9,55,326,7,29]。
   • 8 番（元 POP）の取り消し：不明値 Y8 を戻す → [Y8,Y9,55,326,7,29]。
   • 7 番（元 PUSH）の取り消し：最上位を取り出す → 取り出された値は Y8（よって P6 = Y8）。残り [Y9,55,326,7,29]。
   • 6 番（元 PUSH）の取り消し：取り出されるのは Y9（P5 = Y9）。残り [55,326,7,29]。
   • 5 番（元 PUSH）の取り消し：取り出されるのは 55（P4 = 55）。残り [326,7,29]。
   • 4 番（元 PUSH）の取り消し：取り出されるのは 326（P3 = 326）。残り [7,29]。
   • 3 番（元 POP）の取り消し：取り戻す値を Y3 とする → [Y3,7,29]。
   • 2 番（元 PUSH）の取り消し：取り出されるのは Y3（P2 = Y3）。残り [7,29]。
   • 1 番（元 PUSH）の取り消し：取り出されるのは 7（P1 = 7）。残り [29]（これは初期スタックの唯一の要素と一致）。
6. 以上より 1 番目の PUSH が積んだ値は 7 と確定。選択肢は イ。

選択肢別の誤答解説

• ア: 29
  → 29 は初期スタックにあった下端の値であり、1 番目の PUSH が積んだ値ではない。逆追跡でも最後に残る初期要素として扱われる。
• イ: 7
  → 逆順で取り消すと P1 に対応する取り出し値が 7 になり、論理的に正しい。
• ウ: 326
  → 326 は 4 番目の PUSH（上から数えて対応するP3）が積んだ値であり、1 番目の PUSH ではない（逆追跡で P3 = 326 と示される）。
• エ: 55
  → 55 は別の PUSH（逆追跡で P4 = 55）に対応する値。1 番目の PUSH ではない。

よくある誤解

• 初期スタックを「空」と仮定する
  → この問題では初期状態は不明だが、命令数と最終要素数から初期要素数を算出できる。安易な空仮定は誤りを招く。
• 前進順に漠然とシミュレーションして対応付けを誤る
  → PUSH と POP が交互にある場合、どの PUSH がどの POP に対応するか分かりにくくなる。逆順で「取り消す」方法が明確かつ確実。
• 上下の向きを混同する
  → スタックは LIFO（最後に積んだものが最初に出る）なので、常に「上＝出入口」を意識する。

補足コラム

• 一般解法メモ：
  1. 命令列の PUSH と POP の総数を数え、最終スタックの要素数から初期要素数を求める。
  2. 命令を逆順に「取り消す」ことで、各 PUSH が実際に積んだ値を確定する（PUSH の取り消し＝POP、POP の取り消し＝PUSH）。
     この方法は初期状態が不特定でも一意に戻せる場合に有効です。
• 同じ数値が複数ある場合でも手法は同じで、逆追跡の過程で各 PUSH に固有のインスタンスを対応付けます。

# 逆追跡の簡易実装（プレースホルダは 'Y#' 表示）
final = [192, 55, 326, 7, 29]  # 上から下
# 命令列（前→後）
instr = ["PUSH","PUSH","POP","PUSH","PUSH","PUSH","PUSH","POP","POP","PUSH"]

# 逆順で取り消す
stack = final.copy()
push_ids = []
placeholder_counter = 0
# PUSH を P1..P7 と識別するために順番を先に決める
p_index = 1
for op in instr:
    if op == "PUSH":
        push_ids.append(f"P{p_index}")
        p_index += 1

# 逆順処理
push_iter = list(reversed(push_ids))
mapping = {}  # P? -> value
ph_stack = []  # for placeholders when undoing POPs

for i in range(len(instr)-1, -1, -1):
    op = instr[i]
    if op == "PUSH":
        # undo PUSH -> pop top, assign to corresponding P#
        val = stack.pop(0)  # pop top
        p = push_iter.pop(0)
        mapping[p] = val
    else:  # undo POP -> push a placeholder (value that was popped in forward)
        placeholder_counter += 1
        ph = f"Y{placeholder_counter}"
        stack.insert(0, ph)

# 結果表示（P1.. の対応を確認）
for p in sorted(mapping.keys(), key=lambda x:int(x[1:])):
    print(p, "=", mapping[p])

FAQ