基本情報技術者試験「スタック・キュー」の問題
次の擬似言語は、丸括弧 ( ) と角括弧 [ ] が混在した文字列の対応が正しく取れているかをスタックで判定する手続である。開き括弧は push し、閉じ括弧では頂上の開き括弧と種類が一致するか確認する。文字列 s = "([])[]"（左から1文字ずつ、添字は1から）を与えて実行したとき、戻り値はどれか。match(open,close) は開きと閉じが同種なら真を返す。
○論理型: isBalanced(文字型の配列: s)
スタック: stk // 空で開始
整数型: i
for (i を 1 から sの要素数 まで 1 ずつ増やす)
if (s[i] が '(' または s[i] が '[')
stk.push(s[i])
else
if (stk が空)
return false
endif
if (match(stk.pop(), s[i]) が false)
return false
endif
endif
endfor
if (stk が空)
return true
else
return false
endifアfalse（途中で型不一致）
イtrue（対応が取れている）
ウfalse（スタックに残留あり）
エ判定不能でエラー停止する
正解
イ．true（対応が取れている）
( [ ] ) [ ] を順に処理すると、各閉じ括弧が直前の同種の開き括弧と一致して pop され、走査終了時にスタックは空になる。型不一致も残留もないため true となり、イが正しい。
?選択肢ごとの解説
ア ×いずれかの閉じ括弧が異種の開き括弧と対応するなど型不一致が起きたと誤認した判定で、本データでは閉じ括弧は必ず同種と対応するため不一致は生じない。
イ ○( [ ] ) [ ] を順に処理すると、各閉じ括弧が直前の同種の開き括弧と一致して pop され、走査終了時にスタックは空になる。型不一致も残留もないため true となり、イが正しい。
ウ ×開き括弧が閉じられず残ると考えた誤りだが、本データは開き 3 個・閉じ 3 個が全て対応し残留しない。
エ ×空スタックで閉じ括弧を読むと return false で正常に終わるため、エラー停止には至らない。
✎くわしく
複数種類の括弧では『数が合う』だけでなく『種類が入れ子で正しく対応する』ことが必要である。スタック頂上と閉じ括弧の種類照合（match）が単なる個数カウントとの違いを生む核心である。
✓本番での押さえどころ
試験のコツ
閉じ括弧ごとに『頂上は同じ種類か』を確認し、最後にスタックが空かを必ず見る。
覚え方
『最後に開いたものを最初に閉じる』入れ子の性質をスタックの LIFO と結びつける。
よくある誤り
開き・閉じの個数だけ数えて種類照合を忘れ、([)] のような交差を true と誤判定するミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0098