【JavaScript】() or {} or []がちゃんと閉じられているかのアルゴリズム問題を解いてみた

こんにちは、kazuです。
本日は面白そうだなと思いアルゴリズム問題解いてみたのでコード紹介します。

どういう問題かどうか?

まずはどういう問題かどうかについてです。
タイトルに書いてあるので大体理解していると思いますが、改めて説明をしますね!

()or{}or[]のかっこがちゃんと閉じられていた時はtrueを返しかっこが綴じれていない場合はfalseを返しないさい。
以下参考
① “(){}[]”:true ②”({})”:true ③”({)}”:false ④”(()))”:false ⑤”(}”:false
※小文字半角の前提で全角などは必ず入らない想定です。

という問題になります。

実際にコードを確認してみよう!

ということで実際にコードを確認していきましょう!

// () or {} or [] のみが入る
// booleanを返す
// "(){}[]", true "({})", true "({)}",false "(()))",false "(}",false
let str = "{[][]{}[()]}"
console.log("結果 : ",main(str));

function main(str){
  if (str.length % 2 == 1) {
    console.log("文字列が奇数");
    return false;
  }

  let kakko = []
  let kakkoClose = []
  let tyukakko = []
  let tyukakkoClose = []
  let daikakko = []
  let daikakkoClose = []
  let strArr = str.split(/(?!$)/u)
  for (let i = 0; i < strArr.length; i++) {
      switch(str[i]) {
        case "(":
          kakko.push(str[i]);
          break
        case "{":
          tyukakko.push(str[i]);
          break
        case "[":
          daikakko.push(str[i]);
          break
        case ")":
          kakkoClose.push(str[i]);
          break
        case "}":
          tyukakkoClose.push(str[i]);
          break
        case "]":
          daikakkoClose.push(str[i]);
          break
      }
  }

  console.log("kakko : ",kakko);
  console.log("kakkoClose : ",kakkoClose);
  console.log("tyukakko : ",tyukakko);
  console.log("tyukakkoClose : ",tyukakkoClose);
  console.log("daikakko : ",daikakko);
  console.log("daikakkoClose : ",daikakkoClose);
  console.log("strArr : ",strArr);
  if (kakko.length != kakkoClose.length ||
      tyukakko.length != tyukakkoClose.length ||
      daikakko.length != daikakkoClose.length) {
        console.log("かっこの数が一致しない場合");
        return false;
      }
  for (i = 0; i < strArr.length; i++) {
    console.log("i",i)
    if (strArr[i+1]=="("||
        strArr[i+1]=="{"||
        strArr[i+1]=="[") {
      console.log("ループ対象の次のかっこが ( or { or [ の場合は次のループに行く");
      console.log("今の対象 : ",strArr[i]);
      console.log("次の対象 : ",strArr[i+1]);
      continue;
    }
    if (strArr[i]==")"||
        strArr[i]=="}"||
        strArr[i]=="]") {
      console.log("ループ対象のかっこが ) or } or ] の場合は次のループに行く");
      console.log("今の対象 : ",strArr[i]);
      continue;
    }
    if ( strArr[i] == "(" && strArr[i+1] == ")" ||
         strArr[i] == "{" && strArr[i+1] == "}" ||
         strArr[i] == "[" && strArr[i+1] == "]") {
          console.log("かっこが一致した場合は次のループに行く");
          i += 2;
          continue;
        } else {
          return false;
        }
  }
  return true;
}

解説をしていく

ちょっとだけ解説をしていきます。
まずは3つの処理を入れています。

①文字数が奇数である場合

そもそも奇数の場合は全てのかっこが綴じられていないですよね。
この時点で判定はfalseです。
ex. “([])}” etc..

②かっこの初めとかっこのとじの数が一致した時

これもそうですよね。初めかっこととじかっこの数が違うということは
種類の違うかっこで綴じられているということなのでこの時点で判定はfalseです。
ex. “(}” etc..

③しっかりかっこが綴じられているかのチェック

最後にこのロジックが一番難しかったです。というか結構時間がかかりました。笑
かっこの中にかっこが入ったりと色々と想定されます。それをどうすれば全てチェックするかをしたものが最後のロジックになります。
そしてこの条件に当てはまらないものについてがチェックで綴じられていないものつまりtrueになるものです。
ex. “[({)}]” , “[(({})([)])]” , “}{” etc..

最後に

いかがでしたでしょうか?
今回はアルゴリズム問題を解いてみました。
もしかしたら転職活動とかで実装問題として出てくるかも。。
最後までご覧いただきありがとうございました。