0

一个函数形如
(operator arg1 arg2 ... argn)
即操作符号,参数1参数2一直到参数n。其中参数本身也可以是一个这样格式的函数。
比如这样一串字符串
String="(add (add 1 2) (mul 2 1) 2 )"
要把它的操作数和参数分割出来,即分割成

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

这样的字符数组,应该如何分割?

目前我的做法是每次先把最外边的括号去掉,然后想用空格分割字符串,可是这样中间的空格也会成为要分割的地方。如果用正则表达式,因为每一个参数内部还是可能嵌套括号,这种情况应该如何匹配呢?

查看全部 2 个回答

1

已采纳

前缀表示法S-表达式Lisp表达式

lisp的S-表达式是多层嵌套的树形结构,比较接近抽象语法树(AST)

正则如果没有递归语法的话,很难解析S-表达式

下面是个python的简单例子,我做了注释,应该很容易理解。

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]
>>> 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