Arith-eval(常见的lisp:温和的介绍)

Question

我正在学习Common Lisp:一个温和的介绍,想要解决所有的练习.

有时我有不同的解决方案.它使我困惑,我不能轻易理解本书的标准答案.

例如,用arith-eval:

我的解决方案是:

(defun arith-eval (x)
  (cond
    ((atom x) x)
    (t (eval (cons (cadr x) 
               (cons (car x)
                 (list (arith-eval (caddr x)))))))))

这本书的解决方案:

(defun arith-eval (exp)
  (cond ((numberp exp) exp)
        (t (funcall (second exp)
             (arith-eval (first exp))
             (arith-eval (third exp))))))

在这种情况下我该怎么办？

Answer 1

您的解决方案是a)不正确,b)使用错误的方法.

正确性

您的函数支持表达式(1 + (2 + 3)),但不支持((1 + 2) + 3).

CL-USER 6 > (arith-eval '((3 * 5) + 1))

Error: Illegal car 3 in compound form (3 * 5).

在编写这样的解决方案时,您需要考虑可能的算术表达式以及您的代码是否可以计算解决方案.另外,考虑有用的测试用例并运行它们是个好主意:

CL-USER 14 > (defparameter *test-cases*
               '( ( ((1 + 2) + 3) . 6)
                  ( (1 + 2 + 3)   . 6)
                  ( (1 + (2 + 3)) . 6)))
*TEST-CASES*

CL-USER 15 > (loop for (test . result) in *test-cases*
                   collect (list (ignore-errors (eql (arith-eval test)
                                                     result))
                                 test))
((NIL ((1 + 2) + 3))    ; failed
 (NIL (1 + 2 + 3))      ; failed, but probably not required
 (T   (1 + (2 + 3))))

途径

您的代码创建一个Lisp表单,然后调用eval,并以递归方式执行.

解决Lisp练习的第一条规则:不要使用EVAL

有一个更好的方法:

• 由于表达式中的运算符符号已经是有效的Lisp函数,因此可以调用它并提供正确的参数.我们可以利用内置的评估并通过arith-eval递归调用来计算参数.这是书中的解决方案.

仍然可能有一个eval有意义的解决方案:

• 将整个表达式从中缀转换为前缀一次,然后调用eval(这里eval可以有意义).

有点像(eval (infix-to-prefix expression)).

现在必须编写该函数infix-to-prefix.