中置記法から後置記法に変換

電卓を作る問題を解決方法として後置記法にしてまともに計算してしまうのがいいかなと思って挑戦中。
まぁ、プログラミング初学者が通る道ですね。

アルゴリズムは以下の通り

演算子用のスタックA、数式用のスタックBの二種類がある。

1. 入力された数式を前から順番にとっていく。
2. とった値が数字ならBに詰む。
3. 演算子だったら、Aに既に詰まれている演算子と比較して
   1. 優先順位の高い物だったら、そのままその演算子をAに詰む。
   2. 同じ優先順位か低いものの場合は、BにAのスタックから演算子を下ろす。そして、Aにとってきた演算子を詰む。

という動作を繰り返せばOK。

Lispだと美しく書けたりするのかなぁとwebをあさって居たら
http://d.hatena.ne.jp/ibaza/20070605/1181023708
の方がやっていたのだが
どうもバグがあるっぽかったので手直ししてみた。(RPN '(1 + (2 * 3)))のような式が実行できない。

元のソースを参考にしつつ自分流に書き直すことにしてみた。
以下がソース。

(defun RPN (exp &optional (op nil) (stack nil))
  (cond ((and (null exp)
	      (null op))
	 (flatten (nreverse stack)))
	
	((null exp) (RPN exp (cdr op) (push (pop op) stack)))
	
 	((numberp (car exp))
 	 (RPN (cdr exp) op (push (car exp) stack)))
	
	((consp (car exp))
	 (RPN (cdr exp) op (push (RPN (car exp)) stack )))
	
	((and (not (null op))
	      (<= (weight (car exp))
		  (weight (car op))))
	 (RPN (cdr exp) (push (car exp) (cdr op)) (push (car op) stack)))
	
	((atom (car exp))
	 (RPN (cdr exp) (push (car exp) op) stack))
	))

(defun flatten (x)
  (labels ((rec (x acc)
             (cond ((null x) acc)
                   ((atom x) (cons x acc))
                   (t (rec (car x)
                           (rec (cdr x) acc))))))
    (rec x nil)))

(defun weight (in)
  (case in
    (- 1)
    (+ 1)
    (* 2)
    (/ 2)
    ))

実行結果

ちゃんと望み通りの物ができた。
あとは、これを評価する評価器を作れば電卓は解決。

CL-USER>  (RPN '((1 * 3) + 2 * (2 + 3)))
(1 3 * 2 2 3 + * +)
CL-USER> (RPN '(1 + (2 * 3)))	      
(1 2 3 * +)