java - 如何分割形狀如(operator arg1 arg2 ... argn)的字串？

Question

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

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

這樣的字元數組，該如何分割？

目前我的做法是每次先把最外邊的括號去掉，然後想用空格分割字串，可是這樣中間的空格也會成為要分割的地方。如果用正規表示式，因為每一個參數內部還是可能嵌套括號，這種情況該如何匹配？

Answer 1

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

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

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

下面是個python的簡單例子，我做了註釋，應該很容易理解。

<code>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 ' \n\t' and not in_str: # 空白符
            if word:
                sexp[-1].append(word)
                word = ''
        elif char == '"': # 双引号,字符串起止的标记
            in_str = not in_str
        else:
            word += char # 不是以上的分隔符,就是个合法的标记
    return sexp[0]
</code>

<code>>>> 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')]</code>

S-expression

Answer 2

正規：

<code>\(\s*\w+(\s+\d+)+\s*\)|\w+|\d+</code>

注意，此正規則帶有Global參數

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