whyisyoung's Blog

If you can not persist, you will never succeed :)

Recursive Resolution of Parentheses Balancing

| Comments

好久没更,内疚感爆棚…

1. Problem

Source: Coursera Functional Programming Principles in Scala Week1 Exercise2

输入:以 List[Char] 形式给出的一个字符串,判断其左右括号是否匹配。

输出:true or false

要求:必须使用递归算法

函数原型:def balance(chars: List[Char]): Boolean

示例:

(if (zero? x) max (/ 1 x)) => true

I told him (that it’s not (yet) done). (But he wasn’t listening) => true

:-) => false

())( => false

2. Analysis

括号匹配是很常见的一类题目, 拿到手最容易想到的就是, 时间复杂度是 O(n),很简单。

下面是用栈实现的括号匹配:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool is_matched(const char *str)
{
    stack<char> s;

    while(*str) {
        if(*str == '(')
            s.push('(');
        else if(*str == ')') {
            if(!s.empty())
                s.pop();
            else // 说明当前这个 ) 找不到匹配的 ( 了
                return false;
        }
        str++;
    }

    return s.empty();
}

但是现在题目要求用递归算法实现,于是我们就该考虑如何定义子问题了。

使用一个变量 count 来记录匹配情况,初始未读入字符串时,count = 0。定义子问题 f(str, count),其中 str 为指向字符串的指针,count 表示匹配情况。字符全部读入后, count = 0 则表明匹配,否则不匹配。

每当读入一个字符时,若为 ‘(‘, 则递归调用 f(str++, count++), 若为 ‘)’ 时, 则递归调用 f(str++, count--) , 其他字符则递归调用 f(str++, count), 但无论何时都要保证 count >= 0

尽管知道了算法,但用 Scala 写起来还是困难重重,例如函数原型不可修改,这样 count 也就无法递归使用,但是知道了函数里面可以再定义一个函数,这个问题就迎刃而解了。

对于 List[Char] 给出了几个有用的函数:

chars.isEmpty: Boolean returns whether a list is empty

chars.head: Char returns the first element of the list

chars.tail: List[Char] returns the list without the first element

需要注意的地方有控制流部分,Scala 的某一句返回值并不是指整个函数就立刻返回了,如果还有其他可以执行的语句,Scala 仍然会执行。因此下面这段代码使用了 if…else if… 的结构。

另外在使用 List 的 diff 函数时偶然发现了 Scala 支持纯函数的特性之一 : Immutability (不变性) – 偏向固定的引用以及具有不变的数据结构,一旦创建便不可修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
   * Notice: diff doesn't modify the original List only return a new List --Immutable
   *
   */
  def balance(chars: List[Char]): Boolean = {

    def isMatch(chars: List[Char], count: Int): Boolean = {
      if (count < 0) false

      // If you use "if" not "else if" below, 
      // the function get false last step and still will run this line not return
      else if (chars.isEmpty) (count == 0)
      else if (chars.head == '(') {
        isMatch(chars.tail, count + 1);
      } else if (chars.head == ')') {
        isMatch(chars.tail, count - 1);
      } else {
        isMatch(chars.tail, count);
      }
    }

    isMatch(chars, 0)
  }

Scala 是一门很好玩的语言,总感觉有一些新的思维在里面。上次导师项目中期答辩落下了学习,有待进一步研究。

reference: 面试题之括号匹配

Comments