分析遞迴結構

假設我們想將下面的資料

(A ((B (C D)) (E F)))

根據括號的順序以產生下面的結果

(C D)
(B (C D))
(E F)
((B (C D)) (E F))
(A ((B (C D)) (E F)))

該怎麼做呢？

一開始花了一點時間思考， 始終沒辦法得到一個簡潔的結果， 突然想起之前好像看過這個問題， 印象中要用 stack 來解，有了這個想法之後，結果不到 3 分鐘就解決了，解答如下

data = '(A ((B (C D)) (E F)))'
lpr = []
for i, c in enumerate(data):
     if c == '(':
         lpr.append(i)
     if c == ')':
         k = lpr.pop()
         print data[k:i+1]

方法很簡單，遇到左括號就把該字元的 index 存在 lpr 這個 stack 中， 碰到右括號就 pop lpr，意即把 lpr 最後一個進來的元素 k 拿掉， 然後再印出從 k 到右括號之間的字元， Python 的內建型態 list 本身就提供有關 stack 運算的函式， 所以寫起來非常簡潔， enumerate 函式之前有介紹過。 。

後來又覺得這種分析遞迴結構的問題， 應該用遞迴函式來寫最為直接，就想用遞迴函式來實做。 不過可能是平常已經習慣 for 迴圈了，一開始還不太適應遞迴的思考邏輯， 花了一點時間才想出解法，困擾我的地方在於， 不知道遞迴函式的輸入參數跟輸出要選什麼， 經過一番修修改改之後，終於找到答案， 這是一個練習遞迴的好問題，想練功的人可以試試。

def parse(data, i):
     j = i+1
     while data[j] != ')':
         if data[j] == '(':
             j = parse(data, j) + 1
         else:
             j += 1
     print data[i:j+1]
     return j

parse(data, 0)

演算法其實也不難， 輸入參數 i 是開始的 index， index j 的初始值就是 i+1， 之後如果沒有碰到右括號，j 在 while 迴圈中就會一直加 1； 如果碰到右括號，函式就會回傳右括號的 index； 如果在 while 迴圈中碰到左括號，就呼叫函式， 輸入參數就是左括號的 index，而函式的傳回值之後要取代 j 以保證 j 會一直往下個字元移動。

比較迴圈跟遞迴兩種實作方法， 會發現遞迴其實是一種變相的迴圈， 經由一直呼叫自己，形成類似迴圈的動作。 什麼時候開始及結束遞迴函式很容易判斷， 左括號是開始而右括號是結束。 遞迴的另一個特點是不需要 lpr 這個 stack， 原因也很清楚，因為遞迴是靠輸入及輸出來傳遞字元的位置。 如何控制字元的移動，是我覺得遞迴比較難寫的地方， 這部分好像沒有迴圈來得直接，不曉得是不是因為我比較熟悉迴圈的原因。