読者です 読者をやめる 読者になる 読者になる

中置記法→前置・後置記法

common lisp algorithm

コンパイラの本を流し読みしていたら、中置記法とか前置記法とか後置記法とかが出てきた。

これらの記法間の変換処理(正確には中置記法から後置記法への変換)は、だいぶ前に実装しようとして挫折(?)したことがあったのだが、今日試してみたら、(適切なコードかどうかはともかく)実装できたので、ソース一式を載せておく。

なお、実際に作成したのは、中置記法→後置記法への変換関数と、中置記法→前置記法への変換関数の二つ。

実装

準備

各パーサ(変換処理)を実装する前に、中置記法で記述された文字列をトークンに分割する関数(及びその関連関数)を作成しておく。 ※必要最低限度の実装となっているため、実用的ではない。しかし、修正・拡張もそれほど難しくはないはず。

;;; 述語関数
;; 引数の文字が演算子かどうか
(defun operator? (c) (find c '(#\+ #\- #\* #\/)))

;; 引数の文字が括弧かどうか
(defun parenthesis? (c) (find c '(#\( #\))))

;; 引数が開き括弧かどうか 
(defun open-paren? (obj) (eq obj '\())

;;; 
;; #\0〜#\9 => 数字
;; その他   => シンボル
(defun read-from-char (c)
  (if (digit-char-p c)
      (- (char-code c) (char-code #\0))
    (intern (string c))))

;;;
;; 文字列infixをトークンに分割する
;; この実装では、一文字を一トークンとして扱っており、空白は無視している
(defun tokenize (infix)
  (loop FOR c ACROSS infix
        UNLESS (char= c #\Space)
        COLLECT
        (list (read-from-char c)
              (cond ((operator?    c) :OP)     ; operator         : 演算子
                    ((parenthesis? c) :PA)     ; parenthesis      : 括弧
                    (t                :VA))))) ; value or variable: 演算数?

;;;
> (tokenize "1*2 + (3 - 4)")
--> (1 :VA) (* :OP) (2 :VA) (+ :OP) (|(| :PA) (3 :VA) (- :OP) (4 :VA) (|)| :PA))


中置記法を扱う場合、演算子の優先順位を考慮する必要があるので、そのための関数も定義しておく。

;; 演算子に優先順位(スコア)をつける
;; 値が高い方が、優先順位も高い
(defun priority (op)
  (case op
    ((* /) 2)
    ((+ -) 1)
    (t 0)))

(defun priority< (op1 op2)
  (< (priority op1) (priority op2)))
中置記法→後置記法

中置記法から後置記法への変換。
結果は*standard-output*に出力される。
参照: nlet

;; 終了トークン
;; 中置記法→前置記法の変換でも使う
(defconstant END-TOKEN '(|)| :PA))

;; 中置記法→後置記法
(defun infix2postfix (infix)
  (let ((tokens (tokenize infix)))
    (nlet self (op-stack)
      (destructuring-bind (x type) (or (pop tokens) END-TOKEN)
        (case type
          ;; 演算数の場合
          ;;   1] 演算数を出力
          ;;   2] 優先順位を考慮してop-stack内の演算子を出力
          (:VA (format t "~A " x)
               (self (pop-operators op-stack (caar tokens))))

          ;; 演算子の場合
          ;;   1] op-stackに演算子を追加
          (:OP (self (cons x op-stack)))

          ;; 括弧の場合
          ;;   1] 開き括弧なら、
          ;;   2-1] 次の閉じ括弧までを再帰的に処理(self呼び出し)
          ;;   2-2] 演算数の2と同様  ※括弧で囲まれた部分は、複合的な演算数とも考えられる
          (:PA (when (open-paren? x)
                 (self '())
                 (self (pop-operators op-stack (caar tokens))))))))))

;; スタック(ops)に積まれた演算子の処理
;;   先頭の演算子がnext-op(後続の演算子)よりも優先順位が高い場合は、
;;   その演算子を出力して、スタックから取り除く
(defun pop-operators (ops next-op)
  (if (or (null ops)
          (priority< (first ops) next-op))
      ops
    (progn (format t "~A " (first ops))
           (pop-operators (rest ops) next-op))))

;;;
> (infix2postfix "(1+2*(3-5)+5)/2+5*6-9")
1 2 3 5 - * + 5 + 2 / 5 6 * + 9 -  ;出力結果
--> NIL

括弧と演算子の優先順位に気を付ければ案外簡単。

中置記法→前置記法

中置記法から前置記法への変換。
結果は、S式として返される。

;; 中置記法→前置記法
(defun infix2prefix (infix)
  (let ((tokens (tokenize infix)))
    (nlet self (op lexp) ; op: operator,  lexp: left expression
      (destructuring-bind (x type &aux (rexp x)) (or (pop tokens) END-TOKEN)
        (case type
          (:VA (if lexp
                   (if (priority< op (caar tokens))
                        ;; opの優先順位が低い場合は,opは括弧の外に配置される. (op lexp (... rexp ...))
                       `(,op ,lexp ,(self nil rexp))
                     ;; opの優先順位が高い場合は,opは括弧の内に配置される. (... (op lexp rexp) ...)
                     (self nil `(,op ,lexp ,rexp)))
                 ;; lexpがnullの場合は、rexpをlexpとして次のループへ
                 (self nil rexp)))

          ;; 演算子を設定
          (:OP (self x lexp))

          ;; 開き括弧の場合は、selfを再帰的に呼び出した結果(S式)を、rexpに設定して、次のループへ
          ;; 閉じ括弧ならループ終了. 作成したS式を返す
          (:PA (if (open-paren? x)
                   (progn 
                     (push `(,(self nil nil) :VA) tokens)
                     (self op lexp))
                 lexp)))))))

;;;
> (infix2prefix "(1+2*(3-5)+5)/2+5*6-9")
--> (+ (/ (+ 1 (+ (* 2 (- 3 5)) 5)) 2) (- (* 5 6) 9))

> (eval *)
--> 22

以上。

後置記法と前置記法

中置→後置変換も、中置→前置変換も基本的な構造は、ほとんど同じだった。

二つはまとめられるかもしれないと思い、上のコードをいじっていたら、infix2prefixでlistを作成する時に、opの位置を変更すれば後置記法の結果が返って来ることに気がついた。
前置記法と後置記法の違いは、演算子の位置の違いだけ?

;; infix2prefixとほぼ同じ
(defun infix2postfix (infix)
  (let ((tokens (tokenize infix)))
    (nlet self (op lexp)
      (destructuring-bind (x type &aux (rexp x)) (or (pop tokens) END-TOKEN)
        (case type
          (:VA (if lexp
                   (if (priority< op (caar tokens))
                       `(,lexp ,(self nil rexp) ,op) ; <- opの位置が末尾に
                     (self nil `(,lexp ,rexp ,op)))  ; <- こっちも
                 (self nil rexp)))
          (:OP (self x lexp))
          (:PA (if (open-paren? x)
                   (progn 
                     (push `(,(self nil nil) :VA) tokens)
                     (self op lexp))
                 lexp)))))))

;;;
> (infix2postfix "(1+2*(3-5)+5)/2+5*6-9")
--> (((1 ((2 (3 5 -) *) 5 +) +) 2 /) ((5 6 *) 9 -) +)

> (flatten *)
--> (1 2 3 5 - * 5 + + 2 / 5 6 * 9 - +)

;;;
;; flatten
(defun flatten (lst)
  (nlet-acc self ((x lst))
    (if (consp x)
	(progn (self (car x)) (self (cdr x)))
      (when x
	(accumulate x)))))

このinfix2postfixの実装もちゃんと動いているようだが、新旧の実装で結果が異なっているのが、少し気になる。一応両方共、(gforthを使って)正しい後置式であることは確認しているが...