PROSAGA码农传奇-lisp-在Racket / Scheme中将文本解析为树

<div class =“post-text”itemprop =“text”>
  
    原始方法的问题在于您正在尝试直接移植一个命令式解决方案，即使用pass-by-reference来跟踪遍历的状态。这是行不通的，第一步是以功能编程的方式重新思考解决方案。
  
  
    我们必须跟踪我们在嵌套结构中的位置的这些问题可以使用a更好地解决
    
      堆
    
     数据结构。我会用的
    
      名单
    
     实现一堆列表，使用以下帮助器在最顶层的列表中追加一个新元素：
  
   <pre>
 <code>
 (define (append-top ele stack)
 (cons (append (car stack) (list ele))
 (cdr stack)))

</code>
 </pre>
  
    现在为实际的解决方案。假设输入列表格式正确，且数量相同
     <code>
 <
 </code>
     和
     <code>
 >
 </code>
     并按正确的顺序（不执行错误检查）：
  
   <pre>
 <code>
 (define (parse-tree tokens)
 (let parse ([tokens tokens] [stack '(())])
 (cond [(null? tokens)
 ; solution is at the top of the stack, return it
 (car stack)]
 [(eq? (car tokens) '<)
 ; start new sublist at the top of the stack
 (parse (cdr tokens) (cons '() stack))]
 [(eq? (car tokens) '>)
 ; pop top element of the stack, append it to previous
 ; frame, continue with solution where we left it
 (parse (cdr tokens) (append-top (car stack) (cdr stack)))]
 [else
 ; add current element to top of stack
 (parse (cdr tokens) (append-top (car tokens) stack))])))

</code>
 </pre>
  
    它按预期工作！
  
   <pre>
 <code>
 (parse-tree '(1 < 2 < 3 4 > > Z < X >))
=> '(1 (2 (3 4)) Z (X))

</code>
 </pre>
</DIV>