文字列に欠落している中かっこを見つけてください

Question

"（"と "）"のかっこを確認するロジックを記述しましたが、かっこが混在すると問題が発生するようです。これは、括弧の総数を単に比較しているためです。

これは私が書いたもの

function checkParanthesis(str){ 
 
    var depth=0; 
 
    for(var i in str){ 
 
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") 
 
     depth++; 
 
    else if(str[i] == ")" || str[i] == "}" || str[i] == "]") 
 
     depth--; 
 
    } 
 
    
 
    if(depth !==0) return false; 
 
    
 
    return true; 
 
} 
 

 
console.log(checkParanthesis("() test"));

質問です：

しかし、どのように、私は複数の括弧要素を確認することができますか？ （）{} []

例えば、

入力：

"[(]) abcd" // should return false 
"[{()}] test" // should return true 

は（真ていない）falseを返すべき

Answer 1

追跡するスタックとして配列を使用未解決の開き括弧の数：

function checkParanthesis(str){ 
    var stack=[]; 
    for(var i=0; i<str.length; i++){ 
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") 
     stack.push(str[i]); 
    else if(str[i] == ")") { 
     if(stack.pop() != "(") { return false; } 
    } 
    else if(str[i] == "}") { 
     if(stack.pop() != "{") { return false; } 
    } 
    else if(str[i] == "]") { 
     if(stack.pop() != "[") { return false; } 
    } 
    } 

    return !stack.length; 
} 

おそらく、基本的には読みやすくするために、これをクリーンアップすることができますが、：

• あなたが開いブレースを見つけるたびに、スタックに追加します。
• 閉じる中括弧が表示されるたびに、スタックをポップして、スタックの上端が一致する開きブレースであるかどうかを確認します。
  • そうでない場合は、不一致があります。すぐにfalseを返すことができます。
• あなたが最後にそれを作る場合、あなたは、すべてのエラーを発見しませんでしたスタックが空である場合（すなわち、stack.lengthが0ある）trueを返します。

（それはString.prototypeのプロパティを反復するので、私はまた、あなたのi in strループを変更します。）

一つのクリーンアップあなたが行うことができます（私はわからないんだけど、これはコードより読みか行った場合）閉じた文字をキーとして、対応する開始文字を値として、オブジェクトにブレースペアを配置することです。そして、現在の文字がキーinオブジェクトとして存在している場合、参照、そうであれば、スタックをポップし、そのキーマッチの値かどうかを確認：

function checkParanthesis(str){ 
    var stack=[]; 
    var brace_pairings = { ")":"(", "}":"{", "]":"[" }; 
    for(var i=0; i<str.length; i++){ 
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") { 
     stack.push(str[i]); 
    } else if(str[i] in brace_pairings) { 
     if(stack.pop() != brace_pairings[str[i]]) { return false; } 
    } 
    } 

    return !stack.length; 
} 

Answer 2

よりもむしろカウンタは、あなたがスタックを使用することができ、開いた金具が見えるときにトークンをスタックに押し、の場合は閉じ括弧が表示されたときにスタックからポップします。別のタイプのブラケットがスタックの最上部にあるとき、またはスタックが空のときに閉じ括弧が遭遇すると、ストリングはアンバランスです。

（研磨およびテストされていません）このような何か：

function checkParanthesis(str){ 
var stack = []; 
var open; 
for(var i in str){ 
    if(str[i] == "(" || str[i] == "{" || str[i] == "[") { 
    stack.push(str[i]); 
    } 
    else if(str[i] == ")" || str[i] == "}" || str[i] == "]") { 
    if (stack.length == 0) { 
     return false; 
    } 
    open = stack.pop(); 
    if (
     (open == '(' && str[i] != ')') 
     || (open == '[' && str[i] != ']') 
     || (open == '{' && str[i] != '}') 
    ) { 
     return false; 
    } 
    } 
} 

if (stack.length > 0) { 
    return false; 
} 

return true; 
} 

Answer 3

match()アレイ内のすべての括弧を取得するために正規表現を使用して...そして、それぞれのテスト配列の両端を削除するには、

function checkParanthesis(str) { 
 
    //hashmap to compare open/close braces 
 
    var closers = {'[': ']','(': ')','{': '}'}; 
 
    // create braces array 
 
    var parStack = str.match(/\(|\{|\[|\)|\}|\]/g) || []; 
 

 
    if (parStack.length % 2 !== 0) {//must have even number 
 
    return false; 
 
    } else { 
 
    while (parStack.length) { 
 
     // check each end of array against each other. 
 
     if (closers[parStack.shift()] !== parStack.pop()) { 
 
     //mismatch , we're done 
 
     return false; 
 
     } 
 
    } 
 
    return true; 
 
    } 
 

 
} 
 
console.log('no braces ', checkParanthesis("test")); 
 
console.log('matched ', checkParanthesis("() test")); 
 
console.log('mis matched ',checkParanthesis("[(]) abcd")); // should return false 
 
console.log('matched ',checkParanthesis("[{()}] test"));

を設定しました

Answer 4

アレイ/スタック/カウンタアプローチは、左から右へ文字列を読み取ります。別のアプローチは、内側から作業することです。

function checkParanthesis(str){ 
    while (str.indexOf('()')>=0 || str.indexOf('[]')>=0 || str.indexOf('{}')>=0) { 
    str = str.replace('()','').replace('[]','').replace('{}',''); 
    } 
    return str.length===0; 
} 

グローバル置換とループ回数を減らすために、置換部分に正規表現を使用できます。欠点は、目の前のすべてのものから脱出する必要があることです。str.replace(/\(\)/g,'') et.c