応用情報技術者 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