在Clojure中解析infix表达式

Question

我试图通过在线阅读勇敢的克洛尔的书来教我自己，在第7章的末尾，有一个练习来解析一个数学表达式，这个表达式是用注解符号写到S的--表达式，遵循操作符优先规则。

为此，我在Clojure中实现了调车码算法。但是，我不确定我是否以功能的方式完成了这一任务，因为我已经习惯了使用C++和Python等语言进行编程。特别是，我不确定loop操作符的使用是否有效，因为我的编码方式基本上和C++一样，只是在每个循环迭代中使用recur，而不是变异变量。这让它看起来有点重复。

下面是密码。如果有人能看一看，并就如何以一种更地道的功能方式来做这件事，或者其他任何事情，给出建议，那将是非常感激的。

(def operator-precedence {'= 1, '+ 5, '- 5, '* 6, '/ 6})

(defn infix-parse
  "Converts an infix expression to s-expressions in linear time with the
  shunting-yard algorithm."
  [expr]
  (if (list? expr)
    (loop [val-stack ()
           op-stack ()
           remaining expr
           next-op false]
      (if next-op
        (let [prec (if (empty? remaining)
                     ##-Inf
                     (operator-precedence (first remaining)))
              popped (take-while #(>= (operator-precedence %) prec) op-stack)
              result (reduce
                       (fn [[a b & vals] op]
                         (cons (list op b a) vals))
                       val-stack
                       popped)]
          (if (empty? remaining)
            (first result)
            (recur result
                   (cons (first remaining)
                         (drop (count popped) op-stack))
                   (rest remaining)
                   false)))
        (recur (cons (infix-parse (first remaining)) val-stack)
               op-stack
               (rest remaining)
               true)))
    expr))

(defmacro infix
  [form]
  (infix-parse form))

(infix (1 + 3 * (4 - 5) * 10 / 2))
=> -14
(infix-parse '(1 + 3 * (4 - 5) * 10 / 2))
=> (+ 1 (/ (* (* 3 (- 4 5)) 10) 2))

Answer 1

首先，是的，这是功能性的，是的，这是如何正确地使用loop。

。。。在每一个循环迭代中使用recur，而不是变异变量。

这就是loop的意图。您只需通过recur将“修改后的数据”传递给下一次迭代，而不是对变量进行变异。

你也没有滥用def或atoms的副作用，所以这很好。

我对这段代码的主要关注是，它实际上只是一个巨大的函数。没有函数名指示某些代码正在做什么，也没有注释指出任何行的重要性。现在，我个人对将代码分解为函数很执着，但通常也认为它是最佳实践。正如这的回答所指出的(忽略提到“命令式”)：

拥有传递许多思想的大型命令式功能是很难消化和重用的。

我认为这个函数的大小确实使它很难消化。

作为一个极端的反例，这是我一年前写的同样的算法*。它几乎比您的代码长4倍，但更清楚的是，每段代码都在做什么(并且有10行专门用于文档的代码)。代码，如

(-> equation
    (tokenize-equation)
    (infix->RPN-tokens op-attr-map)
    (tokens-to-string)) ; Should arguably be called token->string

即使没有考虑到它所包含的函数名，也可以相当清楚地说明它负责什么。

我不会试图分解您的代码(主要是因为我的手被烧得很严重，输入这一点已经够困难了)，但是如果您看看我的例子，您可能会发现一些灵感，并在粒度上找到了一个中间点。

祝好运

*虽然我的版本没有计算表达式，因为我正在将它转换成字符串，在我的示例中，数据在编译时是不可用的。