1.8 ディスカッションと練習問題 問1.2解答 #62
Description
@spinute 様
はじめに
自分と同じく独学で勉強している人が、理解をきちんとできてるか確認のために、問題を解いてみたものの、解答解説がなくて困っている人を助けられたら良いなと考えております
どこにかけば良いのかわからなかったのでとりあえず、ひとつずつIssuesに入れていきます。
こうしてほしいというご要望があればそれに従います。
第一章のディスカッションと練習問題の問1.1をPythonで解きましたが、現在整え中です。
まずは問1.2から解答と図を書きましたので、確認いただけると幸いです。
考えた解答
[+1, -1,+1, -1]を用意する。+1, -1からなる数列について、+1 を pushに、 -1 を pop に置き換えた操作の列を作る。この場合[push,pop,push,pop]となる。この場合Dyck wordになる。
次に[+1, -1,-1, +1]を用意する。この場合[push,pop,pop,push]となる。このとき配列3番目のpopは、中に何もない状態でpopできないのでDyck wordとならない。
まとめると
このとき「元の数列がDyck wordであること」と「操作を順に実行したとき空のスタックからpopしないこと」が同じになる。
