calculator-clojure

calculator.clj

(ns fpcontest.expression)

(def Term)
(def Factor)

(def ToMod (int (+ 1000000000 7)))

(def toPrint true)

(defn myprintln [& args]
  (if toPrint
    (apply println args)))

(defn EulerDivNonMemoized [^long x ^long p]
  ;; calculates the x ^ p efficiently for large p where p+2 is a prime number.
  (let [ToMod (+ p 2)] ;; ToMod is a prime number.
    (loop [num (long 1) toPow p localX x]
      (if (= 0 toPow) 
        ;; just print out the results before returning num
        (do (myprintln " EulerDiv : " num " for " x p) 
            num)
        (let [squaredX (rem (* localX localX) ToMod) ;; square successively 
              halfToPow (bit-shift-right toPow 1)] ;; half the p successively
          (if (odd? toPow) ;; if toPow is odd then we should multiply the num with squared version.
            (recur (rem (* num localX) ToMod)
                   halfToPow
                   squaredX)
            (recur num halfToPow squaredX)))))))

(def EulerDiv (memoize EulerDivNonMemoized))

(defn Expression [lst]
  ;; Expression  = Term | Term [+-] Expression
  ;; This returns either 1. '(Long) where Long is result or
  ;; would return a 2. '(Long a b c...) where a b and c are furtur part of list
  ;; case 2 would happen when we have a brackets ()
  (let [term (Term lst) ;; first find the Term
        ;; some debugging printing information
        p (myprintln term " term for exp " lst)
        sizeOfTerm (count term)
        ;; expression used for evaluating Term [+-] Expression
        evaluateExpr (fn [opr lst]
                       ;; opr is + or - or binary operator
                       ;; lst is a seq which would be like '(4 + ...)
                       ;; where ... is some calculator to be evaluated sequence.
                       (let [expr (Expression (drop 2 lst)) ;; evaluate the sequence
                             ;; some debugging info.
                             p (myprintln expr " expr for Expr " lst " and " opr)
                             firstOperand (first lst)] ;; take the first operand
                         ;; always take the mod of result
                         ;; and think it like '(4 + 2 * 8 + 2) would be fed to above call to Expression
                         ;; and would return expr <- '(4 + 16 + 2) and we want to return  '(20 + 2) back
                         (cons (rem (opr firstOperand
                                         (first expr)) ;; second operand is (first expr) 
                                    ToMod) 
                               (rest expr))))]
    ;; if there is more to Term when it returned - this means that we need to do Term [+-] Expression
    (if (> sizeOfTerm 2)
      (if (= (second term) "+")
        (evaluateExpr + term)
        (if (= (second term) "-")
          (evaluateExpr - term)
          ;; it can come here.. in case of ')'
          (if (= (second term) ")")
            term
            ;; ok we should never come here as after the Term it should be + or - or )
            (println "Wrong implementation Expression : " lst))))
      (if (and (= sizeOfTerm 2) (not (= (second term) ")")))
        (println "Wrong implementation Expressoin : size 2 : " lst)
        ;; first of term is the answer
        term))))


(defn Term [lst]
  ;; Term = Factor | Factor [*/] Term
  ;; This returns either 1. '(Long) where Long is result or
  ;; would return a 2. '(Long a b c...) where a b and c are furtur part of list
  ;; case 2 would happen when we have a brackets ()
  (let [factor (Factor lst) ;; First calculate the Factor
        ;; my debugging information
        p (myprintln factor " factor for term " lst)
        sizeOfFactor (count factor)
        evaluateExpr (fn [opr lst]
                       ;; if you read the comments in Expression then you just have to change the + - to 
                       ;; * / only and this should be easy to understand.
                       (let [term (Term (drop 2 lst))
                             ;; some debugging info
                             p (myprintln term " term for expr " lst " and " opr)
                             firstOperand (first lst)]
                         (cons (rem (opr firstOperand
                                         (first term)) 
                                    ToMod) 
                               (rest term))))]
    (if (> sizeOfFactor 2)
      (if (= (second factor) "*")
        (evaluateExpr * factor)
        (if (= (second factor) "/")
          ;; in case of division thing got a little turn as we just can not do simple divide.
          ;; we know by euler that a/b mod p == (a * ((b^(p-2)) mod p)) mod p
          (let [expr (Term (drop 2 factor))
                fExpr (first expr)] 
            (cons (rem (* (first factor) (EulerDiv fExpr (- ToMod 2)))
                       ToMod) (rest expr)))
          ;; should be * / after Factor or ')'
          (if (some #(= (second factor) %) '("+" "-" ")"))
            factor
            (println "Wrong Implementation Term : " lst))))
      (if (and (= sizeOfFactor 2) (not (= (second factor) ")")))
        ;; we need two operators : after operator and operand should be another operator
        (println "Wrong Implementation size 2 Term : " lst)
        factor))))

(defn Factor [lst]
  ;; Factor = [+-] Number | Number | ( Expression )
  (let [firstToken (first lst) ;; judge on the basis of first item of list
        p (myprintln " Factor has : " lst)]
    (if (= firstToken "+")
      ;; convert to positive integer
      (cons (int (Integer. (second lst))) (rest (rest lst)))
      (if (= firstToken "-")
        ;; convert to nevative integer and return e.g. '(- 2 + 3) -> '(-2 + 3) 
        ;; notice that - and 2 were separate part string tokens list and now first item of list 
        ;; is an int.
        (cons (- (int (Integer. (second lst)))) (rest (rest lst)))
        (if (= firstToken "(")
          ;; remove the '(' and evaluate the expression
          (let [expr (Expression (rest lst))]
            ;; returned expession is assumed to be like  3 ) + ...
            ;; remove ')' also
            (cons (first expr) (drop 2 expr))
            )
          ;; make the first one as integer
          (cons  (int (Integer. (first lst))) (rest lst))
          ;;(myprintln "I do not know where i am... " lst)
          )))))

(defn split-with-delim [d s]
  ;; splitter that keeps the delimeters
  (clojure.string/split s 
                        (re-pattern (str "(?=" d 
                                         ")|(?<=" d
                                         ")"))))

(defn make-calulator-list [s]
  ;; given a string like "34+-34" make it as a token of '("34" "+" "-" "34")
  (->> s
       (split-with-delim #"[\/\+\-\*\(\) ]")
       ;; remove empty or spaces.
       (filter #(not (or (= "" %) (= " " %))))
       ;; may be this would help in optimization.
       doall
       ))

(defn StartRun [FuncToCall inputParse outputParse]
  (let [lines (line-seq (java.io.BufferedReader. *in*))]
    (outputParse (FuncToCall (inputParse (first lines)))))
  )  

(StartRun Expression
        make-calulator-list
        (fn [x] (println (int (mod (first x) ToMod)))))