0

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

前回の説明

参照コード
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が偶数の時、stackにbracketPosition+1、つまり()[]{}のいづれかの閉じカッコがpushされる
        if (bracketPosition %2 === 0) {
            stack.push(brackets[bracketPosition+1]);
        }
        else if (stack.pop() !== bracket) {
            return false;
        }
    }
    // スタックが空っぽでないを返す
    return !stack.length;
  }

上記コードの以下の箇所について意味をきちんと理解したいと思っています。

else if (stack.pop() !== bracket) {
            return false;

前回の説明にて

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

との説明をしていただいたのですが、
以下の認識は正しいでしょうか?アドバイスいただけますと幸いです。

bracketが閉じカッコであるとき、例えばその閉じカッコが")"だとします。
そのときstack.pop() !== ")" となるわけですが
この時点でstackには何が入っているのでしょうか?
自分の推測ですと
Stackにはなにも入っていない。
ゆえにstack.popは空っぽという認識でおりますが、正しいでしょうか?

追記

下記の通り、for文のあとにconsole.logを仕込んで
DevToolsで確認してみたのですが
すいません、ちょっと意味が分かっておりません。

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

  verify('a(aabbbccc');



VM1444:11 []
VM1444:11 []
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
VM1444:11 [")"]
false
4
  • 3
    推測ではなく、実際にコードを試した結果は確認されましたか?
    – cubick
    Commented 2020年10月19日 5:25
  • お返事ありがとうございます。確認したのですが、すいません、結果を見ても意味が分かりませんでした。そもそもデバッグの方法が悪いのでしょうか?追記させていただいたのでご確認いただけますと幸いです。
    – ligtning
    Commented 2020年10月19日 12:51
  • 3
    質問のタイトルには、質問の内容を表してください。願望しか書かれていません。
    – htb
    Commented 2020年10月19日 23:48
  • 1
    失礼しました。こちら再編集させていただきました。
    – ligtning
    Commented 2020年10月20日 4:33

1 件の回答 1

1

bracketPosition = brackets.indexOf(bracket);

には「括弧文字を探す」「括弧文字の開く閉じるを区別する」の2つの役目があります。 bracketPosition が非負の時括弧文字であり、偶数の時は開く、奇数の時は閉じる、です(ここんところOK?)

if (bracketPosition %2 === 0)

入れ子あり=括弧は何個開いてもよいわけで、開括弧を見つけたときには判定は不要というか不可能です。閉括弧を見つけたときのために、括弧の種類を push しておけばよいわけです。このソースコードにおいては ( を見つけたときには )push していることに注意({ 発見時に }push 以下同様)
上記処理が bracketPosition%2==0 のとき行われるのは理解できていますか?

そこまで理解できたなら、閉括弧を見つけたつまり bracketPosition%2==0 でないとき即ち else 側に来た時の処理は明白でしょう。「正しい入れ子」とは「最後に見つけた開括弧を閉じる括弧文字がある」ということであり、なおかつ stack には今「対応するべき閉括弧文字」が積まれているわけです。

閉括弧文字を見つけたとき stack.pop()) が取り出された(ということは最も近い開括弧が ( であったということ)その見つけた閉括弧文字が ) でないとは即ち入れ子になっていないので即 return false; してよいってことです。

んで、最後の文字まで来たときには開括弧が残っていない、すなわち stack.length0 であることを確認すれば命題成立です(括弧文字が全くない特別例もこれに含まれる)

1
  • ありがとうございます。理解できました!
    – ligtning
    Commented 2020年10月23日 7:19

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

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