0

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

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

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

日本語にしますと

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

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

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

よろしくお願いします。

追記

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

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が−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;
}

具体的には

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

  stack = [];

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

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

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

  return !stack.length;

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

2
  • 問題文にある文章 Implement function verify(text) which verifies whether parentheses within text are correctly nested. で検索するとよろしいかと思います。
    – user39889
    Commented 2020年10月16日 7:53
  • ありがとうございます。検索したところ答えが見つかったのですが いくつか意味のわからない箇所がありました。追記させていただいたので、もしよろしければ、お時間ある時にでもアドバイスいただけますと幸いです。何卒よろしくお願いいたします。
    – ligtning
    Commented 2020年10月17日 2:01

2 件の回答 2

2

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

つまり、

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

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

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

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

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

stack = [];

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

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

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

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

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

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

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

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

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

  return !stack.length;

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

3
  • ありがとうございます。問題の意味は理解できました!検索したところ答えが見つかったのですが いくつか意味のわからない箇所がありました。追記させていただいたので、もしよろしければ、お時間ある時にでもアドバイスいただけますと幸いです。何卒よろしくお願いいたします。
    – ligtning
    Commented 2020年10月17日 2:04
  • 長くなるので回答の方に追記しますね。 Commented 2020年10月17日 8:07
  • ありがとうございます。こちらベストアンサーとさせていただきました。 質問を2つしてしまっているので、再度以下のリンクにて質問させていただきました。もしよろしければ、お時間あるときにでも見ていただけますと幸いです。ありがとうございました。 ja.stackoverflow.com/questions/71288/…
    – ligtning
    Commented 2020年10月17日 17:22
1

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

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

は専門外なので後は任せた

1
  • ありがとうございます。問題の意味は理解いたしました!助かりました!
    – ligtning
    Commented 2020年10月17日 2:03

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

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