有效大括号 - CodeWars 挑战

Question

代码战有一个挑战，要求您检查一串圆括号、方括号和花括号是否有效。

如果所有大括号都与正确的大括号匹配，则认为一串大括号有效。

即"()"是有效的，"[(])"不是。

"(){}[]"是有效的，"[({})](]"不是。等等。

我已经能够创建一些逻辑来检查是否有正确数量的左大括号和右大括号。

尝试：

function validBraces(braces) {

  let parenCount = 0;
  let squareBracketCount = 0;
  let curlyBraceCount = 0;

    for (let i =0; i < braces.length; i++) {
      let character = braces[i];
        if (character === "(") {
          parenCount -= 1;
          }
        if (character === ")") {
          parenCount += 1;
          }
        if (character === "[") {
          squareBracketCount -= 1;
          }
        if (character === "]") {
          squareBracketCount += 1;
        }
        if (character === "{") {
          curlyBraceCount -= 1;
        }
        if (character === "}") {
          curlyBraceCount += 1;
        }
      }
      if (parenCount === 0 && squareBracketCount === 0 && curlyBraceCount === 0) {
        return true;
      } 
      else {
        return false;
      }
}

但是我一直无法想出一种方法来检查在下一种类型的支架打开之前打开支架是否“关闭” 。

也许是这样的？

if (
  (firstChar === "(" && lastChar === ")") ||
  (firstChar === "{" && lastChar === "}") ||
  (firstChar === "[" && lastChar === "]")
) {
  return true;
} else {
  return false;
}

但是，这必须根据我的其他if-statement...（？）

编辑：理解这一挑战的关键是，右大括号必须直接在左大括号之后出现，或者它必须“平行”——与另一个对称。

Answer 1

您实际上不需要在这里使用数组，您可以只使用正则表达式和递归：

const regex = /\(\)|\[\]|\{\}/;
const validBraces = braces => regex.test(braces)
  ? validBraces(braces.replace(regex, ''))
  : '' === braces

console.log(validBraces('{{}}')) // true
console.log(validBraces('{{[]}}')) // true
console.log(validBraces('{[{}]}')) // true
console.log(validBraces('({{}})')) // true
console.log(validBraces('{[()]}')) // true
console.log(validBraces('{{}[}')) // false
console.log(validBraces('{{]}}')) // false
console.log(validBraces('{}}')) // false
console.log(validBraces('{({}}')) // false
console.log(validBraces('((}}')) // false
console.log(validBraces('}[)}')) // false

Answer 2

您可以使用array跟踪以前出现的左大括号，一旦出现任何结束标记，您需要将其与数组的最后一个值匹配（如果匹配）则弹出最后一个值，否则返回 false，最后如果您留下了与空数组返回 true 否则返回 false

function validBraces(braces){
  let tracer = []
  for(let i=0;i < braces.length; i++){
    if ( braces[i] === "(" || braces[i] === "{" || braces[i] === "["){
      tracer.push(braces[i])
    } else{
      if(tracer.length === 0) return false
      let lastValue = tracer[tracer.length-1]
      if( (braces[i] === ']' && lastValue === '[') || (braces[i] === '}' && lastValue === '{') || (braces[i] === ')' && lastValue === '('))
      {
        tracer.pop()
      } else {
        break;
      }
    }
  }
  return tracer.length === 0
}


console.log(validBraces( "()" )) // true
console.log(validBraces( "[]" )) // true
console.log(validBraces( "{}" )) // true
console.log(validBraces( "(){}[]" )) // true
console.log(validBraces( "([{}])" )) // true
console.log(validBraces( "(}" )) // false
console.log(validBraces( "[(])" )) // false
console.log(validBraces( "({})[({})]" )) // true
console.log(validBraces( "(})" )) // false
console.log(validBraces( "(({{[[]]}}))" )) //true
console.log(validBraces( "{}({})[]" )) // true
console.log(validBraces( ")(}{][" )) // false
console.log(validBraces( "())({}}{()][][" )) // false
console.log(validBraces( "(((({{" ))  // false
console.log(validBraces( "}}]]))}])" )) // false