scala 如何递归地平衡括号

How to balance parenthesis recursively

提问by Greg K

I'm working on some code to balance parenthesis, this questionproved most useful for the algorithm.

我正在编写一些代码来平衡括号，这个问题被证明对算法最有用。

I implemented it in my first language (PHP) but I'm learning Scala and trying to convert the code.

我用我的第一语言 (PHP) 实现了它，但我正在学习 Scala 并尝试转换代码。

Here is my PHP code:

这是我的 PHP 代码：

function balanced($string) {
  return isBalanced($string, "");
}

function isBalanced($chars, $stack) {
  if (!strlen($chars))
    return empty($stack);

  switch ($chars[0]) {
    case '(':
      // prepend stack with '(', move to next character
      return isBalanced(substr($chars, 1), $chars[0] . $stack);
    case ')':
      // if '(' seen previously, shift stack, move to next character
      return !empty($stack) && isBalanced(substr($chars, 1), substr($stack, 1));
    default:
      // do nothing to stack, move to next character
      return isBalanced(substr($chars, 1), $stack);
  }
} 

I've test this, it works. However, when I convert it to Scala, it fails on balanced strings.

我已经测试过了，它有效。但是，当我将其转换为 Scala 时，它在平衡字符串上失败。

My Scala code:

我的斯卡拉代码：

object Main {
  def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], stack: String): Boolean = {
      if (chars.isEmpty)
        stack.isEmpty
      else if (chars.head == ')')
        balanced(chars.tail, chars.head + stack)
      else if (chars.head == '(')
        !stack.isEmpty && balanced(chars.tail, stack.tail)
      else
        balanced(chars.tail, stack)
    }

    balanced(chars, "")
  }
}

I appreciate this isn't the best Scala code but I'm just starting out. Some tests:

我很欣赏这不是最好的 Scala 代码，但我才刚刚开始。一些测试：

balance("(if (0) false (x))".toList) - fails
balance("profit and loss (P&L).\n(cashflow)".toList) - fails
balance(":)".toList) - passes
balance(")(()".toList) - passes

The PHP equivalent passes all these tests. What have I done wrong in my Scala implementation?

PHP 等效项通过了所有这些测试。我在 Scala 实现中做错了什么？

回答by Aaron Novstrup

For what it's worth, here's a more idiomatic Scala implementation:

对于它的价值，这里有一个更惯用的 Scala 实现：

def balance(chars: List[Char]): Boolean = {
  @tailrec def balanced(chars: List[Char], open: Int): Boolean = 
    chars match {
      case      Nil => open == 0
      case '(' :: t => balanced(t, open + 1)
      case ')' :: t => open > 0 && balanced(t, open - 1)
      case   _ :: t => balanced(t, open)
    }

  balanced(chars, 0)
}

回答by Greg K

Just for completeness, I found an even more terse 'scala-esque' implementation from another SO question:

为了完整起见，我从另一个 SO 问题中找到了一个更简洁的“scala-esque”实现：

def balance(chars: List[Char]): Boolean = chars.foldLeft(0){
  case (0, ')') => return false
  case (x, ')') => x - 1
  case (x, '(') => x + 1
  case (x, _  ) => x
} == 0

回答by Vigneshwaran

Same as Aaron Novstrup's answer but using 'if else'. I'm also attending the same course but we are taught upto if/else only so far.

与 Aaron Novstrup 的回答相同，但使用“if else”。我也在参加同一门课程，但到目前为止我们只学过 if/else。

def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], open: Int): Boolean = 
      if (chars.isEmpty) open == 0
      else if (chars.head == '(') balanced(chars.tail, open + 1)
      else if (chars.head == ')') open > 0 && balanced(chars.tail, open - 1)
      else balanced(chars.tail, open)
    balanced(chars, 0)
}

回答by Kim Stebel

You have mixed up the cases for (and ).

你混淆了案件的(和)。

回答by Chaitanya Kumar

Instead of using Switch case you can use recursion to solve your problem in an efficient way.

您可以使用递归以有效的方式解决问题，而不是使用 Switch case。

Following is my code to achieve the same with the help of recursion. You need to convert the string to List for my method.

以下是我在递归的帮助下实现相同目标的代码。对于我的方法，您需要将字符串转换为 List。

Code :

代码 ：

object Balance {

  def main(args: Array[String]): Unit = {
    var paranthesis = "(234(3(2)s)d)" // Use your string here
    println(bal(paranthesis.toList)) // converting the string to List 
  }

  def bal(chars: List[Char]): Boolean ={
   // var check  = 0
    def fun(chars: List[Char],numOfOpenParan: Int): Boolean = {
      if(chars.isEmpty){
        numOfOpenParan == 0
      }
      else{
        val h = chars.head

        val n = 
          if(h == '(') numOfOpenParan + 1
          else if (h == ')') numOfOpenParan - 1
          else numOfOpenParan 

       // check  = check + n
        if (n >= 0) fun(chars.tail,n)
        else false 
      }
    }
    fun(chars,0)
  }
}

回答by Rey619

Adding to Vigneshwaran's answer (including comments & filtering unnecessary letters to avoid extra recursive calls):

添加到 Vigneshwaran 的答案（包括评论和过滤不必要的字母以避免额外的递归调用）：

def balance(chars: List[Char]): Boolean = {
  @scala.annotation.tailrec
  def recurs_balance(chars: List[Char], openings: Int): Boolean = {
    if (chars.isEmpty) openings == 0
    else if (chars.head == '(') recurs_balance(chars.tail, openings + 1)
    else openings > 0 && recurs_balance(chars.tail, openings - 1)
  }

  recurs_balance(chars.filter(x => x == '(' || x == ')'), 0)
}

回答by Anuj Mehta

My solution for this

我的解决方案

def balance(chars: List[Char]): Boolean = {
 var braceStack = new Stack[Char]()

def scanItems(strList:List[Char]):Boolean = {
   if(strList.isEmpty)
       braceStack.isEmpty
   else{
      var item = strList.head
      item match {
        case '(' => braceStack.push(item)
                    scanItems(strList.tail)
        case ')'=> if(braceStack.isEmpty){
                        false
                    }
                    else {
                      braceStack.pop
                      scanItems(strList.tail)
                    }
        case _ => scanItems(strList.tail)
      }
    }
 }

 scanItems(chars)

}

}

回答by sivaji kondapalli

  val myStack = new Stack[Char]

  def balance(chars: List[Char]): Boolean = {
    def processParanthesis(x: Char, a: List[Char]): Stack[Char] = {
      if (x == '(') {
        myStack.push('(');
      } else if (x == ')') {
        if (!myStack.empty())
          myStack.pop();
        else
          myStack.push(')');
      }
      if (a.length == 0)
        return myStack;
      else
        return processParanthesis(a.head, a.tail);
    }
    return processParanthesis(chars.head, chars.tail).empty();
  }

回答by user62058

It seems we are attending the same course. my solution:

看来我们上的是同一门课。我的解决方案：

def balance(chars: List[Char]): Boolean = 
doBalance(chars, 0) == 0;
def doBalance(chars: List[Char], parenthesisOpenCount: Int): Int =
if(parenthesisOpenCount <0) -100;
else
if(chars.isEmpty) parenthesisOpenCount
else
  chars.head match {
  case '(' => return doBalance(chars.tail, parenthesisOpenCount+1) 
  case ')' => return doBalance(chars.tail, parenthesisOpenCount-1)
  case _ => return doBalance(chars.tail, parenthesisOpenCount)
}