調車碼算法

Question

我正在Clojure中實現一箇中綴計算器，該工具從我開始實施Dijkstra的調車碼算法開始。我認爲我把它做得很好，但是開玩笑對我來說，它似乎並不能很好地處理操作員。致電(shunting-yard "3 + 5")=>(\3)。就這樣。有人能告訴我在這裏處理操作符時出了什麼問題嗎？

(import '(java.lang.Character)) 

(defn operator? [sym] 
    "Determines if a given token is a mathematical operator." 
    (some #{sym} '(\+ \- \* \/ \% \^ \!))) 

(defn associativity-of [operator] 
    "Determines the associativity of a given mathematical operator." 
    (if (some #{operator} '(\+ \- \* \/ \%)) 
    'left 
    'right)) 

(defn precedence-of [operator] 
    "Determines the precedence of a given mathematical operator." 
    (case operator 
     (\+ \-) 2 
     (\* \/ \%) 3 
     (\^ \!) 4 
        0)) 

(defn operator-actions [stmt stack] 
    "Actions taken when the next token in the stmt is an operator." 
    (let [token-prec (precedence-of (first stmt)) 
     token-assoc (associativity-of (first stmt)) 
     stack-oper (first stack) 
     stack-prec (precedence-of stack-oper)] 
    (cond (or (and (= token-assoc 'left) 
        (<= token-prec stack-prec)) 
       (and (= token-assoc 'right) 
        (< token-prec stack-prec))) 
      (cons stack-oper (shunt stmt (rest stack))) 
      :else (shunt (rest stmt) (cons (first stmt) stack))))) 

(defn stack-operations [stack] 
    "Actions to take if (nil? stmt)" 
    (comment "If a left paren is found on the stack, it means 
      that there was no right paren to match it, and 
      therefore the statement had unbalanced parentheses.") 
    (cond (and (not (nil? stack)) 
      (= (first stack) \()) (print "Unbalanced parentheses.\n") 
     (nil? stack)() 
     :else (cons (first stack) (stack-operations (rest stack))))) 

(defn shunt [stmt stack] 
    (cond (empty? stmt) (stack-operations stack) 
     (Character/isDigit (first stmt)) (cons (first stmt) 
               (shunt (rest stmt) stack)) 
     (operator? (first stmt)) (operator-actions stmt stack) 
     (= (first stmt) \() (recur (rest stmt) (cons (first stmt) stack)) 
     (= (first stmt) \)) (if (= (first stack) \() 
           (recur (rest stmt) (rest stack)) 
           (cons (first stack) (shunt stmt (rest stack)))))) 

(defn shunting-yard [stmt] 
    (shunt stmt())) 

Answer 1

我真的不知道該調度場算法（保存在維基百科剛剛2分鐘），但一個問題，我看到的是，這shunt不處理的空間。所以它讀取您的\3，遞歸併退出，因爲下一個字符是\space。如果stmt沒有空格，即"3+5"，您會得到StackOverflowError，但這是進步，我想。