0

以下のコードを理解したく思っております。
前回の質問は以下になるのですが、長くなるため、新しく質問させていただきました。

コーディングテストで質問の意味がわかりません。

自分で日本語訳を付けてみましたが
間違い箇所をご指摘いただければ幸いです。
ちなみに言語はJavascriptです。

参照コード
https://gist.github.com/paveleremin/86dafdb4341244fc3a94#file-gistfile1-js-L9-L30

function verify(str){
    // bracketsに()[]{}を代入
    var brackets = "()[]{}",
    // bracket,bracketPositionはなんらかのオブジェクト、stackは配列
        bracket,
        bracketPosition,
        stack = [];
  
    for (var i = 0, l = str.length; i < l; i++) {
      // 引数srtのインデックス番号をbracket変数に代入
        bracket = str[i];
  
        // bracketPosition変数にbrackets(つまり()[]{})がbracket(つまりstr)の中にあるか探す機能のメソッドを代入(ある場合はカッコのインデックスを返す)
        bracketPosition = brackets.indexOf(bracket);
        // bracketPositionが−1を返す(つまりstrの中に()[]{}がない)場合は次の繰り返し処理を開始
        if (bracketPosition == -1) continue;
        // bracketPositionが2の倍数で割り切れる時、以下不明
        if (bracketPosition %2 === 0) {
            stack.push(brackets[bracketPosition+1]);
        }
        // そのほかはスタックの中の最後の要素とbracketが一致しない場合はfalseを返す
        else if (stack.pop() !== bracket) {
            return false;
        }
    }
    // スタックが空っぽを返す
    return !stack.length;
  }

特にコード中にある

stack.push(brackets[bracketPosition+1]);

が理解できておりません。

stack.push(brackets)ならわかるのですが
stack.push(brackets[bracketPosition+1])
[bracketPosition+1]はどういう意味になりますでしょうか?

また、関数は引数strの文字列にカッコが閉じられているかどうか調べる関数なのですが
なぜスタックを使うとstrの文字列を調べられるのかがわかっておりません。

追記1

アドバイス、ご指摘ありがとうございます。
私の方で以下を勘違いしているのかもしれません。

brackets.indexOf(bracket);

これはbrackets、つまり()[]{}が、bracket(引数strのこと)の中にあるか探すという意味で
捉えているのですが、まずはこちらは正しいでしょうか?

そして、前回の回答文と今回に回答文の下記の文言がしっくりきていません。

前回の回答文:ループでbrackets配列の文字を順番に取り出して、bracketに入れています。その位置が2で割り切れるとき、というのは括弧の最初の文字"(","[","{"を指します。

今回の回答文:前回の質問でも回答されている通り偶数であれば開カッコであるといえます.例えば,striが'['であればこれは2です。

bracketは引数strのことなので
例えば引数strがa(aabbb)cccだとします。
書き換えるとこうです。

()[]{}.indexOf(a(aabbb)ccc)

indexOfは、文字列の中に指定した文字があるか探して、あればその位置を返してくれるので
"("のIndex番号は1になります。

そして

bracketPosition = brackets.indexOf(bracket)とあるので
bracketPosition = 1

になります。

上記の分で間違っている箇所はございますでしょうか?

0

1 件の回答 1

2

stack.push(brackets)ならわかるのですが
stack.push(brackets[bracketPosition+1])
[bracketPosition+1]はどういう意味になりますでしょうか?

bracketPositionbrackets.indexOf(bracket)なので,マッチした文字がbracketsの何文字目かが入っています.
前回の質問でも回答されている通り偶数であれば開カッコであるといえます.例えば,str[i](strのi+1文字目)が'['であればこれは2です.
このとき,brackets[bracketPosition]は当然ながら[です.そして,brackets[bracketPosition+1]bracketsの次の文字……つまり対応する閉じカッコとなるので]です.これをスタックの最後に置いておきます.

else if (stack.pop() !== bracket)は,bracketPositionが奇数のとき,つまりbracketが閉じカッコであるときに呼び出されるコードです.スタックの最後から取り出し(popすると当然取り出した値はスタックから消えます),それを期待する閉じカッコbracketと比較します.
もし,期待する閉じカッコではない閉じ括弧であれば期待する条件を満たさないことが確定するのでfalseを返して終わるわけです.

最後の文字までループを回すと,条件をみたしていればスタックは空になっていることが期待されます.スタックにデータが残っていれば(stack.length0でないならば),まだ閉じられていない括弧があるということになるので.

ex: (p: push / o: pop)
aaaa(bbb[cc]dd)aaa
....p...p..o..o...
=> stack = []

aaa(bbb(cc[ddd]ee
...p...p..p...o..
=> stack = [')',')']

なので,スタックの中身が空かどうかが判断条件になるわけです.


ところで,質問文にコードをどこかから転載する場合は出典の明記に努めてください.ソースコードにも著作権はあり,ときに厄介になるので. https://gist.github.com/paveleremin/86dafdb4341244fc3a94#file-gistfile1-js-L9-L30 のコードがほぼ一致しますが.(質問文のコードは謎の追記によるエラー箇所が見受けられますが……)

あと

また、関数は引数strの文字列にカッコが閉じられているかどうか調べる関数なのですが

というのも少し違和感を覚える表現で,「文字列中の括弧の対応が正しいかを調べる表現」のほうがしっくりきます……


追記について

書き換えるとこうです。

()[]{}.indexOf(a(aabbb)ccc)

この時点で認識に誤りがあります。(というか文字列はちゃんとクォーテーションで囲ってくださいね、擬似コードとしても意味が変わってしまいます)

bracketbracket = str[i]です。これはループ内であり、stri文字目です。
str'a(aabbb)ccc'であれば各ループにおいて 'a', '(', 'a', 'a', 'b', 'b', 'b', ')', 'c', 'c', 'c'が順番に入ってきます。ですので、

'()[]{}'.indexOf('(')

のようになります。そして、indexOfの返すn文字目0始まりです
なので、'('のindexは1ではなく0です。

如何でしょうか?

5
  • ありがとうございます。こちら長くなりそうなので 追記分にて不明点を記載させていただきました。もしよろしければ ご覧いただけますと助かります。何卒よろしくお願い申し上げます。
    – ligtning
    Commented 2020年10月17日 23:48
  • @ligtning 追記について追記しました
    – hinaloe
    Commented 2020年10月18日 5:15
  • ありがとうございます。やはり勘違いしていたようですね。とてもよく理解できました。たびたびすいません、stack.pop() !== bracketの部分について追記2として記載させていただいたので、もしよろしければ ご覧いただけますと助かります。何卒よろしくお願い申し上げます。
    – ligtning
    Commented 2020年10月18日 19:37
  • 質問の追加は、別質問を立てられることも検討してください
    – htb
    Commented 2020年10月19日 0:12
  • 1
    失礼いたしました。上記の説明をベストアンサーとさせていただき、以下へ新しく質問を立てさせていただきました。 もしよろしければ ご覧いただけますと幸いです。 ja.stackoverflow.com/questions/71320/…
    – ligtning
    Commented 2020年10月19日 5:02

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。