scala - 试图理解 Scala 中的括号平衡递归

Question

我是 Scala 和函数式编程的新手。免责声明:是的，我正在 Coursera 上学习 Scala 类(class)，是的，这是作业的一部分。我在这里的唯一目标是获得一些帮助以了解此解决方案的工作原理，以便开发我自己的解决方案并熟悉函数式编程。

我坚持执行递归算法来检查括号平衡。我根本不明白:

1. 功能的结构
2. 如何计算 bool 表达式

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

我的第一个疑问如下。内部函数立即从计算 bool 表达式开始

if (chars.isEmpty) open == 0

我的理解(可能是错误的)是这里两个表达式都会被求值:chars.isEmpty 和 open==0。但是，参数 open 似乎还没有在任何地方定义。那为什么我没有得到错误呢？其次，我根本无法得到这条线:

if (chars.head == '(') balanced(chars.tail,open+1)

balanced(chars.tail,open+1) 将在何处评估以及如何评估？

假设我想检查 "(" 是否有平衡括号。

if (chars.isEmpty) open == 0

然后会返回False

if (chars.head == '(') balanced(chars.tail,open+1)

第一个表达式为真，但第二个呢？ “(”没有尾部，而且我也看不到 open+1 是如何工作的，因为整数 open 尚未在任何地方定义。我很漂亮困惑。

Answer 1

您误解了一项基本内容 - 函数定义。让我们跳过程序最初不重要的部分:

def balance(chars: List[Char]): Boolean = {
  def balanced(chars: List[Char], open: Int): Boolean = { /* ... */ }
  balanced(chars,0)
}

注意 balance 函数的第一行只是一个函数定义——它是一个本地函数。一旦控制流到达 balanced(chars, 0) 行，它将调用此函数 - 因此 open 变量将被初始化为 0。

希望这能解决您对“未初始化变量”的担忧。如果您还有其他问题，请发表评论，我会尽力帮助您。