如何在 Common LISP 中递归删除嵌套括号，例如
(unnest '(a b c (d e) ((f) g))) => (a b c d e f g)
(unnest '(a b)) => (a b)
(unnest '(() ((((a)))) ())) => (a)
谢谢
问问题
18457 次
12 回答
25
于 2010-11-01T01:28:28.130 回答
15
(defun flatten (l)
(cond ((null l) nil)
((atom l) (list l))
(t (loop for a in l appending (flatten a)))))
于 2010-04-26T10:13:48.437 回答
8
我意识到这是一个旧线程，但它是我在 google lisp flatten 时出现的第一个线程。我发现的解决方案与上面讨论的类似，但格式略有不同。我会像你刚接触 lisp 一样解释它，就像我第一次用谷歌搜索这个问题时一样，所以其他人很可能也是。
(defun flatten (L)
"Converts a list to single level."
(if (null L)
nil
(if (atom (first L))
(cons (first L) (flatten (rest L)))
(append (flatten (first L)) (flatten (rest L))))))
对于那些刚接触 lisp 的人来说，这是一个简短的总结。
以下行声明了一个名为 flatten 的函数，其参数为 L。
(defun flatten (L)
下面的行检查一个空列表。
(if (null L)
下一行返回 nil 因为 cons ATOM nil 声明了一个包含一个条目 (ATOM) 的列表。这是递归的基本情况，让函数知道何时停止。这之后的行检查列表中的第一项是否是原子而不是另一个列表。
(if (atom (first L))
然后，如果是，它使用递归来创建这个原子的扁平列表，并结合函数将生成的扁平列表的其余部分。cons 将一个原子与另一个列表结合起来。
(cons (first L) (flatten (rest L)))
如果它不是原子，那么我们必须对其进行展平，因为它是另一个列表，其中可能有更多列表。
(append (flatten (first L)) (flatten (rest L))))))
append 函数会将第一个列表追加到第二个列表的开头。另请注意，每次在 lisp 中使用函数时，都必须用括号括起来。起初这让我很困惑。
于 2013-11-14T01:09:11.067 回答
7
您可以像这样定义它，例如：
(defun unnest (x)
(labels ((rec (x acc)
(cond ((null x) acc)
((atom x) (cons x acc))
(t (rec (car x) (rec (cdr x) acc))))))
(rec x nil)))
于 2010-04-21T07:11:35.630 回答
7
(defun flatten (l)
(cond ((null l) nil)
((atom (car l)) (cons (car l) (flatten (cdr l))))
(t (append (flatten (car l)) (flatten (cdr l))))))
于 2010-05-24T02:21:03.533 回答
5
Lisp 有remove删除东西的功能。在这里，我使用了一个版本，该版本REMOVE-IF删除了谓词为真的每个项目。我测试事物是否是括号，如果为真则将其删除。
如果要删除括号，请参阅此功能：
(defun unnest (thing)
(read-from-string
(concatenate
'string
"("
(remove-if (lambda (c)
(member c '(#\( #\))))
(princ-to-string thing))
")")))
但是请注意，正如 Svante 所提到的，通常不会“删除”括号。
于 2010-04-22T09:00:11.067 回答
4
大多数答案已经提到了Flatten问题的递归解决方案。使用 Common Lisp 对象系统的多重分派，您可以通过为 3 种可能的场景定义 3 种方法来递归地解决问题：
(defmethod flatten ((tree null))
"Tree is empty list."
())
(defmethod flatten ((tree list))
"Tree is a list."
(append (flatten (car tree))
(flatten (cdr tree))))
(defmethod flatten (tree)
"Tree is something else (atom?)."
(list tree))
(flatten '(2 ((8) 2 (9 (d (s (((((a))))))))))) ; => (2 8 2 9 D S A)
于 2020-04-08T20:21:19.147 回答
4
当我访问这个问题时，只需将其留在这里，只需要展平一个级别，然后自己弄清楚(apply 'concatenate 'list ((1 2) (3 4) (5 6 7)))在这种情况下这是一个更清洁的解决方案。
于 2020-04-10T17:01:50.187 回答
2
我知道这个问题真的很老，但我注意到没有人使用 push/nreverse 成语，所以我在这里上传。
该函数reverse-atomize取出每个“原子”并将其放入output下一次调用中。最后，它产生一个向后的扁平化列表，由nreverse函数中的atomize函数解析。
(defun reverse-atomize (tree output)
"Auxillary function for atomize"
(if (null tree)
output
(if (atom (car tree))
(reverse-atomize (cdr tree) (push (car tree) output))
(reverse-atomize (cdr tree) (nconc (reverse-atomize (car tree)
nil)
output)))))
(defun atomize (tree)
"Flattens a list into only the atoms in it"
(nreverse (reverse-atomize tree nil)))
所以调用atomize '((a b) (c) d)看起来像这样：
(A B C D)
如果你reverse-atomize用reverse-atomize '((a b) (c) d)这个来打电话会发生：
(D C B A)
人们喜欢使用 、 和 等函数push，nreverse因为nconc他们使用的 RAM 比各自cons的reverse、 和append函数少。话虽这么说，它的双重递归性质reverse-atomize确实伴随着它自己的RAM ifications。
于 2016-02-15T02:00:33.363 回答
2
这是一种基于累加器的方法。本地函数%flatten保留尾部的累加器（列表的右侧部分已经被展平）。当剩余要展平的部分（列表的左侧部分）为空时，它返回尾部。当要展平的部分是非列表时，它会返回以尾部为前缀的部分。当要展平的部分是列表时，它会展平列表的其余部分（使用当前尾部），然后使用该结果作为尾部以展平列表的第一部分。
(defun flatten (list)
(labels ((%flatten (list tail)
(cond
((null list) tail)
((atom list) (list* list tail))
(t (%flatten (first list)
(%flatten (rest list)
tail))))))
(%flatten list '())))
CL-USER> (flatten '((1 2) (3 4) ((5) 6) 7))
(1 2 3 4 5 6 7)
于 2015-10-21T19:06:50.340 回答
2
这个流行的问题只有递归解决方案（不包括 Rainer 的答案）。
让我们有一个循环版本：
(defun flatten (tree &aux todo flat)
(check-type tree list)
(loop
(shiftf todo tree nil)
(unless todo (return flat))
(dolist (elt todo)
(if (listp elt)
(dolist (e elt)
(push e tree))
(push elt flat))))))
于 2020-04-08T20:49:55.053 回答
1
(defun unnest (somewhat)
(cond
((null somewhat) nil)
((atom somewhat) (list somewhat))
(t
(append (unnest (car somewhat)) (unnest (cdr somewhat))))))
于 2012-07-31T10:59:45.570 回答