71246


先日、コーディングテストで以下のような問題が出たのですが、  
問題文の意味が英語ということもあり、よくわかりませんでした。  
ちなみに言語はJavaScriptです。

> Implement function verify(text) which verifies whether parentheses within
> text are  
>  correctly nested. You need to consider three kinds: (), [], <> and only
> these kinds.
[code]

     Examples:
     verify("---(++++)----") -> 1
     verify("") -> 1
     verify("before ( middle []) after ") -> 1
     verify(") (") -> 0
     verify("<( >)") -> 0
     verify("( [ <> () ] <> )") -> 1
     verify(" (   [)") -> 0
    
[/code]

日本語にしますと

> テキスト内の括弧が正しくネストされたかどうかを検証する関数verify（text）を実装します  
>  （）、[]、<>の3種類のみを考慮する必要があります。

とありますが問題文の意味がよくわかりませんでした。  
推測ですが、verify関数の引数の中身にカッコがあるかどうか調べるのではないかと思うのですが確証が持てません。

どなたか質問の意味、そしてそれを解決するために何か参考になる文献などありましたら教えていただけますと助かります。

よろしくお願いします。

_**追記**_

アドバイス頂いたとおりに検索すると  
答えが以下のようにありました。  
ですが、いくつかの箇所が日本語に訳そうとしてもわかりませんでした。

[code]

    function verify(str){
      // brackets、bracket、bracketPositionに()[]{}を代入
      var brackets = "()[]{}",
          bracket,
          bracketPosition,
          // このスタックがなぜ必要なのかわかりません？？？
          stack = [];
    
          // 文字列strに()[]{}が入っているか調べる
          ()[]{}.indexOf(str[i])
    
      for (var i = 0, l = str.length; i < l; i++) {
        // 引数srtのインデックス番号をbracket変数に代入
          bracket = str[i];
    
          // bracketPosition変数にbrackets（つまり()[]{}）がbracket(つまりstr)の中にあるか探す機能のメソッドを代入（ある場合はカッコのインデックスを返す）
          bracketPosition = brackets.indexOf(bracket);
          // bracketPositionが−１を返す（つまりstrの中に()[]{}がない）場合は次の繰り返し処理を開始
          if (bracketPosition == -1) continue;
          // bracketPositionが２の倍数で割り切れる時、つまりカッコがネストされている時、
          // スタックの中に？？？をプッシュする。この？？？の部分がわかりません。
          if (bracketPosition %2 === 0) {
              stack.push(brackets[bracketPosition+1]);
          }
          // そのほかはスタックの中の最後の要素とbracketが一致しない場合はfalseを返す
          else if (stack.pop() !== bracket) {
              return false;
          }
      }
      // スタックが空でないのを返す？？？少し意味がわかりませんでした。
      return !stack.length;
    }
    
[/code]

具体的には

１、// このスタックがなぜ必要なのかわかりません。。。

[code]

      stack = [];
    
[/code]

２、// bracketPositionが２の倍数で割り切れる時、つまりカッコがネストされている時、  
// スタックの中に？？？をプッシュする。この？？？の部分がわかりません。

[code]

      if (bracketPosition %2 === 0) {
          stack.push(brackets[bracketPosition+1]);
      }
    
[/code]

３、 // スタックが空でないのを返す？？？少し意味がわかりませんでした。

[code]

      return !stack.length;
    
[/code]

の箇所です。  
全体文も日本語訳を付けたので  
そちらも含め間違っている箇所をご指摘いただきますと助かります。  
何卒よろしくお願い申し上げます。


CC BY-SA 4.0
2020-10-16T07:43:57.427
71244
2020-10-17T08:28:10.153
2020-10-17T02:00:26.267
39719
39719
question
javascript
コーディングテストで質問の意味がわかりません。


nest
とはコンピュータ業界では「入れ子」と訳します。カッコの中に（別の）カッコがあることを入れ子と言います。で、問題文は入れ子になっているカッコの開く閉じるが正しく対になっているかどうか検証
(=verify) する関数を実装しろってことですね (題意的にカッコ文字以外は無視してよい様子)

`<>` は正しい対  
`( [ <> ] )` は正しい対  
その他、例題において入れ子のカッコが正しく対になっていると `1` なっていないと `0`  
特別例としてカッコが全くないときは `1`

[javascript](/questions/tagged/javascript "'javascript' のタグが付いた質問を表示")
は専門外なので後は任せた


CC BY-SA 4.0
2020-10-16T08:11:43.050
71245
2020-10-16T08:11:43.050
8589
71244
answer


問題文の日本語訳をそのまま解釈すると、(),[],<>の括弧の組み合わせが矛盾なく記述されているかをチェックする関数を作れ、という意味だと思います。

つまり、

１）括弧の開始と終了が対になっている。  
〇 aaaa(bbbbb)cccc  
× aaaa(bbbb(cccc)

２）括弧で囲まれた範囲が別の括弧の範囲と交わらない(内部に含むものはOK)  
〇 aaaa(bbbb[cccc]dddd)  
× aaaa(bbbb[cccc)dddd]

というようなことをチェックすればよいと思います。

質問の追記を受けてですが、

> １、// このスタックがなぜ必要なのかわかりません。。。
[code]

>     stack = [];
>  
[/code]

これは単純に、スタック用の配列を宣言しているだけです。  
今回の問題と混同しそうですが。

>
[code]

>      // brackets、bracket、bracketPositionに()[]{}を代入
>       var brackets = "()[]{}",
>           bracket,
>           bracketPosition,
>           // このスタックがなぜ必要なのかわかりません？？？
>           stack = [];
>  
[/code]

この部分、変数を宣言するのにカンマで区切って行っています。つまり

[code]

    var brackets = "()[]{}";
    var bracket;
    var bracketPosition;
    var stack = [];
    
[/code]

と同じことです。`brackets`は文字列、`bracket`,`bracketPosition`はなんらかのオブジェクト、`stack`は配列です。

> ２、// bracketPositionが２の倍数で割り切れる時、つまりカッコがネストされている時、  
>  // スタックの中に？？？をプッシュする。この？？？の部分がわかりません。
[code]

>      if (bracketPosition %2 === 0) {
>          stack.push(brackets[bracketPosition+1]);
>      }
>  
[/code]

１．の質問と合わせて考えると、ループでbrackets配列の文字を順番に取り出して、bracketに入れています。その位置が2で割り切れるとき、というのは括弧の最初の文字"(","[","{"を指します。つまり、文字列を先頭から調べて、括弧を構成する文字が見つかった場合、それが先頭だったらその文字をstackに入れておく、という処理です。

> ３、 // スタックが空でないのを返す？？？少し意味がわかりませんでした。
[code]

>       return !stack.length;
>  
[/code]

文字列内の括弧がちゃんとルール通り閉じていれば、`stack.length`は0になるはずなので、そうならない場合はエラーと判別できる、ということです。trueとfalseに合わせるため"!"(not)を付けています。


CC BY-SA 4.0
2020-10-16T08:14:47.833
71246
2020-10-17T08:28:10.153
2020-10-17T08:28:10.153
9515
9515
71244
answer