JS括弧マッチング問題
2380 ワード
codewarsの上で括弧の一致するテーマをしました.
テーマ
文字列の中の{}、[]、()の三つの括弧がマッチしているかどうかを判断するには、入れ子の場合を考慮する必要があります.
例:
この問題の最も根本的なものは2つの場合のみであり、1つは並列であり、すなわち嵌合がない場合である.もう一つの場合は、
第一の方法:
第二の方法:
おわりに
データ構造と正規表現は非常に重要であることがわかってきました.(ここでの解決方法はそれぞれ使いました.)普段はあまり使わないですが、応用シーンがあると、データ構造と正規表現の強さが分かります.
テーマ
文字列の中の{}、[]、()の三つの括弧がマッチしているかどうかを判断するには、入れ子の場合を考慮する必要があります.
例:
validBraces("(){}[]") // true
validBraces("(}") // false
validBraces("[(])") // false
validBraces("([{}])") // true
Solutionこの問題の最も根本的なものは2つの場合のみであり、1つは並列であり、すなわち嵌合がない場合である.もう一つの場合は、
()[]{}
のような入れ子の場合である.第一の場合は比較的簡単で、難しいのは第二の場合です.入れ子がある場合の解決方法は、まず一番奥の括弧にマッチすることです.つまり、私達がよく言っているのは内部から崩れます.第一の方法:
function validBraces(braces){
while(/\(\)|\[\]|\{\}/g.test(braces)){
braces = braces.replace(/\(\)|\[\]|\{\}/g,"")
}
return !braces.length;
}
この方法は、ペアの括弧を検索し、隣接する括弧を空の文字列に置換します.つまり削除します.最後に文字列の長さが0かどうかを判断します.はい、完全に一致することを表します.実は、このような方案は典型的な“内部から崩れます”です.{[()]}
を例にとって、今は一番奥の{[()]}
だけがペアで隣接しています.()
を空の文字列に置き換えた後、()
はペアになり、そして空の文字列に置き換えられます.このように、ペアと隣接する括弧が見つからなくなるまでループして検索します.第二の方法:
function validBraces(braces){
let leftBraReg = /[\(\{\[]/,
//
stack = [],
bracket, rightBracket
braces = braces.split('')
for(bracket of braces) {
if(leftBraReg.test(bracket)) {
stack.push(bracket)
}
else {
switch (bracket) {
case ')':
rightBracket = stack.pop()
if(rightBracket !=='(') {
return false
}
break
case ']':
rightBracket = stack.pop()
if(rightBracket !=='[') {
return false
}
break
case '}':
rightBracket = stack.pop()
if(rightBracket !=='{') {
return false
}
break
}
}
}
return stack.length === 0 ? true : false
}
この方法は、左半分の括弧、すなわち[]
、(
、[
をスタックスタックの中に入れ、右側の括弧、すなわち{
、)
、]
、}
に遍歴したときに、スタックの左側の括弧と、巡回した半端の括弧が一致するかどうかを見ることである.遍歴が完了したら、スタックの長さが0であると判断し、マッチングしないとマッチングします.私たちは同様に{[()]}
を例にとって、前の3つの項目、すなわち{
、[
、(
を巡回したときに、スタックの一番上にある'('の後出庫は)
と比較して、一致するかどうかを見ます.後の)
、]
も同じです.おわりに
データ構造と正規表現は非常に重要であることがわかってきました.(ここでの解決方法はそれぞれ使いました.)普段はあまり使わないですが、応用シーンがあると、データ構造と正規表現の強さが分かります.