1

我正在努力在 Common Lisp 中自己写一些东西，实现 Shutting-yard 算法。我认为它没问题，即使它看起来相当丑陋并且如果我怀疑它的 Lispy 特性，但是在测试 REPL 中的函数时，我得到了标题中的错误。

代码如下，测试用例为(shunting-yard '(3 + 5)).

(defparameter *output-queue*   nil)
(defparameter *operator-stack* nil)

(defun determine-precedence (operator)
  (case operator
    (('+ '-) 2)
    (('* '/) 3)
    ('^      4)))

(defun shunting-yard (stmt)
  (loop until (null stmt) do
       (let ((token (car stmt)))
         (cond ((or (numberp token)
            (eq token '\())
            (setf *output-queue* (cons token *output-queue*)))
               ((mapcar #'(lambda (x) (eq token x)) '(+ - * / ^))
            (let* ((token-precedence (determine-precedence token))
                   (stack-topmost (car *operator-stack*))
                   (stack-precedence (determine-precedence stack-topmost)))
              (when (< token-precedence stack-precedence)
                (setf *output-queue* (cons stack-topmost *output-queue*))
                (setf *operator-stack* (cdr *operator-stack*)))
              (setf *operator-stack* (cons token *operator-stack*))))
               ((eq token '\))
            (loop for stack-topmost in *operator-stack*
               until (eq stack-topmost '\()
               do (progn
                (setf *output-queue* (cons stack-topmost *output-queue*))
                (setf *operator-stack* (cdr *operator-stack*)))
               finally (setf *operator-stack* (cdr *operator-stack*)))))
         (setf stmt (cdr stmt))))
  (loop while (not (null *operator-stack*))
     do (progn
      (setf *output-queue* (cons (car *operator-stack*) *output-queue*))
      (setf *operator-stack* (cdr *operator-stack*))))
  (nreverse *output-queue*))

是代码本身的错误（我的猜测）还是在我的测试用例中？

提前非常感谢，这写起来真的很有趣，我迫不及待地想从事其他工作，但只有在我完成这项工作之后。

4

1 回答 1

2

有几个错误：

第一的：

(defun determine-precedence (operator)
  (case operator
    (('+ '-) 2)
    (('* '/) 3)
    ('^      4)))

报价需要去。全部。

第二：

(mapcar #'(lambda (x) (eq token x)) '(+ - * / ^))

以上不是你想的那样。将其替换为对 MEMBER 的调用。

第三：

 (when (< token-precedence stack-precedence)

您需要确保变量确实绑定到数字。使用类似的东西

 (check-type token-precedence number)
 (check-type stack-precedence number)

之前作为检查。

愉快的进一步调试......

于 2011-03-02T06:22:34.640 回答