Scala:确保大括号是平衡的 [英] Scala: Make sure braces are balanced

问题描述

我正在运行一个代码来平衡语句中的括号.我想我已经猜对了，但它在一个特定的陈述中失败了，我需要了解为什么?

I am running a code to balance brackets in statement. I think i have gotten it correct but it is failing on one particular statement, i need to understand why?

这是一个特别失败的测试 "())("

This is the test in particular it is failing "())("

除了编码之外，我认为我需要修复算法，有什么指示吗?

More than the coding i think i need to fix the algo, any pointers?

def balance(chars: List[Char]): Boolean = {

  def find(c: Char, l: List[Char], i: Int): Int={
    if( l.isEmpty ) {
      if(c=='(')
        i+1
      else if(c==')')
        i-1
      else
        i
    }
    else if (c=='(')
      find(l.head, l.tail, i+1)
    else if(c==')')
      find(l.head,l.tail, i-1)
    else
      find(l.head,l.tail, i)

  }

  if(find(chars.head, chars.tail,0) ==0 )
     true
  else
     false

}


balance("())(".toList) //passes when it should fail
balance(":-)".toList)
balance("(if (zero? x) max (/ 1 x))".toList)
balance("I told him (that it's not (yet) done).\n(But he wasn't listening)".toList)

推荐答案

这是一个版本:

def balance(chars: List[Char]): Boolean = {
    def inner(c: List[Char], count: Int): Boolean = c match {
        case Nil                   => count == 0           // Line 1
        case ')' :: _ if count < 1 => false                // Line 2
        case ')' :: xs             => inner(xs, count - 1) // Line 3
        case '(' :: xs             => inner(xs, count + 1) // Line 4
        case _ :: xs               => inner(xs, count)     // Line 5
    }
    inner(chars, 0)
}

所以在您的代码中，我认为您缺少对 count < 的额外检查.1 当你遇到正确的括号时！因此，如果同时检查 ')' 和 count <，则您需要一个额外的 else.1(上面示例代码中的第 2 行)

So in your code, I think you are missing the additional check for count < 1 when you encounter the right paranthesis! So you need an additional else if that checks for both the ')' and count < 1 (Line 2 in the example code above)

这篇关于Scala:确保大括号是平衡的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！