1
\$\begingroup\$

I need to be able to parse simple equations in an app I'm writing, and decided to try writing my own parser. I ended up using the Shunting-Yard Algorithm to convert from infix notation to RPN as the first step. Later, I'm going to write something that can evaluate RPN equations.

I did a lot of manual stuff here. I'm atrocious at using regexes, so all the parsing is done manually. I also learned this algorithm using the pseudocode on Wikipedia, so my literal translation may be naïve.

Tested using: http://www.mathblog.dk/tools/infix-postfix-converter/

Example:

; Defines the operators
(def test-op-attr-map
  {"+" (new-op-attr 1 true),
   "-" (new-op-attr 1 true),
   "*" (new-op-attr 2 true),
   "/" (new-op-attr 2 true)})

(infix->RPN "{1 + 2 / ( 3 - 4)} * 5 - 6 / 7"
            test-op-attr-map)

> "1234-/+5*67/-"

I have a few main concerns:

  • The "main parsing loop", infix->RPN-tokens, is huge. It's basically just dispatching to other functions depending on what the read token is.

  • A lot of my functions return vector pairs. Some steps require "altering" both the operator stack, and the output queue, so it would be difficult to separate the functionality into its own function without returning a pair. Is there a better way to achieve this without shoving everything into infix->RPN-tokens?

  • I don't like how I'm defining "operator maps". The definition of test-op-attr-map above seems overly bloated. I need to be able to store each operator string, along with it's infix precedence, and whether or not it's left-associative. I tried defining the constructor alias new-op-attr for the Operator-Attribute thinking it would help, but I don't think it did.

  • It currently only handles integers. I need a more sophisticated numeric? function to handle doubles. I was thinking of something like:

    (defn parse-double? [str-double]
      (try
        (Double/parseDouble str-double)
    
        (catch NumberFormatException e nil)))
    
    ; For readability
    (def numeric? parse-double?)
    

    But it could be argued that this is abusing Double/parseDouble. At this point, speed isn't a factor, at all, so I'm not worried about that. Would this be considered ok?

I'd appreciate any advice on anything else as well though.

(ns parser.shunting
  (:require [clojure.string :as s])

  (:import [java.text ParseException]))

(defrecord Operator-Attribute [precedence left-assoc?])

(def new-op-attr ->Operator-Attribute)

(defn- parsing-error ^IllegalArgumentException [^String message]
  (IllegalArgumentException.
    (str "Problem while parsing: " message)))

(defn- numeric? [str-or-char]
  (if (char? str-or-char)
    (Character/isDigit ^Character str-or-char)
    (every? numeric? str-or-char)))

(def ^:private left-bracket?
  #{"(" "[" "{"})

(def ^:private right-bracket?
  #{")" "]" "}"})

(defn- resolve-right-brace
  "Pops the stack onto the output queue while the popped operator isn't a left-bracket.
  Returns a pair of [popped-stack updated-output].
  Throws an IllegalArgumentException if a left bracket isn't found."
  [op-stack output-queue]
  (loop [[popped-op & rest-stack] op-stack
         acc-output output-queue]
    (cond
      (nil? popped-op)
      (throw (parsing-error "Mismatched right bracket."))

      (left-bracket? popped-op)
      [rest-stack acc-output]

      :else
      (recur rest-stack (conj acc-output popped-op)))))

(defn- resolve-operator
  "Pops operators from the stack to the output queue while the popped operators are left associative and have a higher precedence than op.
  Returns a pair of [popped-stack updated-output]"
  [op op-stack output-queue op-attr-map]
  (let [{op-prec :precedence} (op-attr-map op)]
    (loop [[popped-op & rest-ops :as acc-stack] op-stack
           acc-output output-queue]
      (if popped-op
        (let [{pop-op-prec :precedence, pop-op-l-assoc? :left-assoc?}
              (op-attr-map popped-op)
              pushed-output (conj acc-output popped-op)]

          (if (and pop-op-l-assoc? (>= pop-op-prec op-prec))
            (recur rest-ops pushed-output)
            [(conj acc-stack op) acc-output]))

        [(conj rest-ops op) acc-output]))))

(defn- infix->RPN-tokens [tokens op-attr-map]
  (loop [op-stack '()
         [tok & rest-toks] tokens
         output []]
    (cond
      (nil? tok)
      (if (some left-bracket? op-stack)
        (throw (parsing-error "Mismatched left bracket."))
        (into output op-stack))

      (numeric? tok)
      (recur op-stack rest-toks (conj output tok))

      (left-bracket? tok)
      (recur (conj op-stack tok) rest-toks output)

      (right-bracket? tok)
      (let [[updated-stack updated-output]
            (resolve-right-brace op-stack output)]

        (recur updated-stack rest-toks updated-output))

      :else ; Must be an operator. Check against op-attr-map?
      (let [[updated-stack updated-output]
            (resolve-operator tok op-stack output op-attr-map)]

        (recur updated-stack rest-toks updated-output)))))

(defn- remove-first-token
  "Takes a string equation, and splits it on the first token.
  Returns a pair of [token remaining-equation]"
  [^String remaining-equation]
  (let [trimmed (s/triml remaining-equation)
        base-tok (first trimmed)]
    (if (numeric? base-tok)
      (let [pieces (split-with numeric? trimmed)]
        (mapv (partial apply str) pieces))

      [(str base-tok) (subs trimmed 1)])))

(defn- tokenize-equation
  "Takes a string equation and returns a vector of tokens."
  [^String equation]
  (loop [acc-equ equation
         tokens []]
    (if (empty? acc-equ)
      tokens
      (let [[tok rest-equ] (remove-first-token acc-equ)]
        (recur rest-equ (conj tokens tok))))))

(defn- tokens-to-string [tokens]
  ; Realized stupidly after I posted this that this mucks up equations
  ;  if they contain multi-digit numbers
  ; Should really be (s/join " " tokens) instead.
  (apply str tokens))

(defn infix->RPN
  "Takes a equation, and an op-map, and converts the infix equation into RPN representation based on the operator precedences defined by the op-map.
  The op-map is a map of string->Operator-Attribute pairs, where the string is the representation of the operator."
  [^String equation, op-attr-map]
  (-> equation
      (tokenize-equation)
      (infix->RPN-tokens op-attr-map)
      (tokens-to-string)))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.