有效括号 - CodeWars 挑战

Question

有个challenge on codewars让你检查一串括号、括号、花括号是否有效

A string of braces is considered valid if all braces are matched with the correct brace.

即"()" 有效，"[(])" 无效。

"(){}[]" 有效，"[({})](]" 无效。等等

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

尝试:

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

但我无法想出一种方法来检查左大括号 "closes" 是否在下一个 type 大括号打开之前。

也许是这样的？

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

但是这必须根据我的其他检查 if-statement...(?)

编辑：理解这个挑战的关键是右大括号必须直接在左大括号之后或者必须是"parallel" - 与另一个对称.

Answer 1

您可以使用 array 来跟踪之前出现的左大括号，一旦出现任何结束标记，您需要将其与数组的最后一个值匹配，如果它匹配弹出最后一个值 else return false，最后如果剩下空数组 return true else return 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

Answer 2

这里你真的不需要使用数组，你可以使用正则表达式和递归：

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 3

function validBraces(braces){
 while(/\(\)|\[\]|\{\}/g.test(braces)){braces = braces.replace(/\(\)|\[\]|\{\}/g,"")}
 return !braces.length;
}

// double regex

Answer 4

在 scala 中你可以这样做

object Kata {

  def validBraces(s: String): Boolean =
    s.replace("()", "").replace("[]", "").replace("{}", "") match { case "" => true; case `s` => false; case x => validBraces(x) }
}

Answer 5

我已经在 Scala 中完成了一些测试并且它有效。如果字符串的长度是 2 如果不需要输入递归调用，因为在匹配中你已经检查了它是否正确：

   object Kata1{
        def validBraces(s: String): Boolean ={
          var valid: Boolean = true
          if(s.length > 1){
           s(0) match{
              case '('  => if( s(1) == ')' || s(s.length-1) == ')'){
                if(s.length != 2){
                  if(s(1) == ')'){
                    valid = validBraces(s.substring(2, s.length))
                  }else{
                    valid = validBraces(s.substring(1, s.length-1))
                  }
                }
          } else {
                if(s.lastIndexOf(')') != -1){
                 var newS = s.substring(0, s.indexOf(')')).concat(s.substring(s.indexOf(')')+1, s.length))
                  valid = validBraces(newS.substring(1, s.length-1))
                }else valid = false
           }
        case '['  => if( s(1) == ']' || s(s.length-1) == ']') {
         if(s.length != 2){
          if(s(1) == ']'){
           valid = validBraces(s.substring(2, s.length))
         }else{
           valid = validBraces(s.substring(1, s.length-1))
         }
       }
      } else {
       if(s.lastIndexOf(']') != -1){
         var newS = s.substring(0, s.indexOf(']')).concat(s.substring(s.indexOf(']')+1, s.length))
        valid = validBraces(newS.substring(1, s.length-1))
      }else valid = false
    }
    case '{'  => if( s(1) == '}' || s(s.length-1) == '}') {
      if(s.length != 2){
        if(s(1) == '}'){
          valid = validBraces(s.substring(2, s.length))
        }else{
          valid = validBraces(s.substring(1, s.length-1))
        }
      }
    } else {
      if(s.lastIndexOf('}') != -1){
        var newS = s.substring(0, s.indexOf('}')).concat(s.substring(s.indexOf('}')+1, s.length))
        valid = validBraces(newS.substring(1, s.length-1))
      }else valid = false
    }
    case _ => valid = false
  }
  /*if(s.length != 2 && valid){
    if(s(1) == ')'  || s(1) == '}'  || s(1) == ']' ){
      valid = validBraces(s.substring(2, s.length))
    }else{
      valid = validBraces(s.substring(1, s.length-1))
    }
  }*/
}else{
  valid = false
}

if(s.length == 0){
  valid = true
}
valid
 }
 }

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

Answer 6

我的 JavaScript 这个套路的解决方案很容易理解并且通过了所有测试。但我知道它的优化不是 top-notch。它只是一步一步地消除元素：

开始： ( { [] } ) || ( { [] } }
然后： ( {} ) || ( {} }
则：() || (} 完成：清除||剩菜
当length = 0时通过，当length > 0时不通过

   function validBraces(braces){
while(braces.indexOf("{}") !== -1 || braces.indexOf("()") !== -1 || braces.indexOf("[]") !== -1){
    braces = braces.replace("{}", "").replace("()", "").replace("[]", "");
}
return braces.length === 0 ? true: false;

console.log(validBraces("(({{[[]]}}))"));

有效括号 - CodeWars 挑战

Valid Braces - CodeWars Challenge

javascript

string

curly-braces

braces