Алгоритм Маневрового двора - PullRequest
Новая
       21

Алгоритм Маневрового двора

2 голосов
/ 21 апреля 2011

Я работаю над внедрением инфиксного калькулятора в Clojure, который начинается с того, что я реализую алгоритм Дейкстры Шунтирования-ярда.Я думал, что у меня все хорошо, но шутка на меня, похоже, операторы не очень хорошо справляются.Звонок (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 ()))

1 Ответ

3 голосов
/ 21 апреля 2011

Я на самом деле не знаю алгоритм Shunting-Yard (сэкономьте 2 минуты в Википедии сейчас), но я вижу одну проблему в том, что shunt не обрабатывает пробелы.Таким образом, он читает ваш \3, рекурсив и выходит, поскольку следующий символ равен \space.Если stmt не имеет пробелов, то есть "3+5", вы получите StackOverflowError, но это прогресс, я думаю.

...