問題描述

一個函數(shù)形如(operator arg1 arg2 ... argn)即操作符號，參數(shù)1參數(shù)2一直到參數(shù)n。其中參數(shù)本身也可以是一個這樣格式的函數(shù)。比如這樣一串字符串String='(add (add 1 2) (mul 2 1) 2 )'要把它的操作數(shù)和參數(shù)分割出來，即分割成

['add','(add 1 2)','(mul 2 1)','2']

這樣的字符數(shù)組，應(yīng)該如何分割？

目前我的做法是每次先把最外邊的括號去掉，然后想用空格分割字符串，可是這樣中間的空格也會成為要分割的地方。如果用正則表達式，因為每一個參數(shù)內(nèi)部還是可能嵌套括號，這種情況應(yīng)該如何匹配呢？

問題解答

前綴表示法， S-表達式，Lisp表達式

lisp的S-表達式是多層嵌套的樹形結(jié)構(gòu)，比較接近抽象語法樹(AST)。

正則如果沒有遞歸語法的話，很難解析S-表達式。

下面是個python的簡單例子，我做了注釋，應(yīng)該很容易理解。

def parse_sexp(string): sexp = [[]] word = ’’ in_str = False #是否在讀取字符串 for char in string: # 遍歷每個字符if char == ’(’ and not in_str: # 左括號 sexp.append([])elif char == ’)’ and not in_str: # 右括號 if word:sexp[-1].append(word)word = ’’ temp = sexp.pop() sexp[-1].append(tuple(temp)) # 形成嵌套elif char in ’ nt’ and not in_str: # 空白符 if word:sexp[-1].append(word)word = ’’elif char == ’'’: # 雙引號,字符串起止的標(biāo)記 in_str = not in_strelse: word += char # 不是以上的分隔符,就是個合法的標(biāo)記 return sexp[0]

>>> parse_sexp('(+ 5 (+ 3 5))')[(’+’, ’5’, (’+’, ’3’, ’5’))]>>> parse_sexp('(add (add 1 2) (mul 2 1) 2 )')[(’add’, (’add’, ’1’, ’2’), (’mul’, ’2’, ’1’), ’2’)]

S-expression

正則：

(s*w+(s+d+)+s*)|w+|d+

注意，此正則帶有Global參數(shù)

如果arg1, arg2, arg3, ... argn中嵌套(op arg ...)只有一層的話，可以用這個方法