中置記法から前置記法の変換

Scheme

僕はSchemerなので、演算子の優先順位とかよくわかりません。

だから、悪の中置記法を前置に変えてしまえばハッピーになると思うんだよ。


と思ったけど、これが結構むじぃ。


まずは定義。

式   ::= 項 ([+-] 項)*
項   ::= 因子 ([*-] 因子)*
因子 ::= 数 | '(' 式 ')'

定義どうりに書いてけばいいんだけど、

  • 左側の項を見たとき、残りは何か、その結果は何か。という情報が必要になる。
  • つまり、その場でリストに挿入出来ないので、多値というか継続というかが必要になる。スタックでもよさげ。
  • しかも、「([+-] 項)*」というように連続がある。

結構めんどい。

(define (infix->list ex)
  (letrec
    ((factor (lambda (ex cont) ; factor ::= number | '(' term ')'
               (cond ((null? ex) (cont '() '()))
                     ((pair? (car ex)) (cont (expr (car ex) (lambda (res exr) res))
                                             (cdr ex)))
                     (else
                       (cont (car ex) (cdr ex))))))
     (make (lambda (next cmp)  ; 何か ::= 次にみる奴 ([比較]次にみる奴)*
             (lambda (ex cont)
               (next ex (letrec ((loop (lambda (res exr)
                                         (if (or (null? exr) (not (member (car exr) cmp)))
                                             (cont res exr)
                                             (next (cdr exr)
                                                   (lambda (r e)
                                                     (loop (list (car exr) res r)
                                                           e)))))))
                                loop)))))
     (term (make factor '(* /))) ; term ::= factor ([*/] factor)*
     (expr (make term '(+ -))))  ; expr ::= term ([+-] term)*
    (expr ex (lambda (res exr) res))))

てすとぉ。

(infix->list '(1)) ; 1
(infix->list '((((((1))))) + 2)) ; (+ 1 2)

(infix->list '(1 * 2 + 3 * 4)) ; (+ (* 1 2) (* 3 4))
(infix->list '(1 + 2 * 3 + 4)) ; (+ (+ 1 (* 2 3)) 4)
(infix->list '((1 + 2) * (3 + 4))) ; (* (+ 1 2) (+ 3 4))

; 括弧のみだとイマイチ微妙な感じ。
(infix->list '(())) ; ()
(infix->list '(() + 2)) ; (+ () 2)

なんかうまくいってるっぽい感じもする。


単項の+-には対応してない。


調子に乗ってきたので、(2 *)を試す。

(infix->list '((2 *))) ; (* 2 ())

うは、ダメすぎ。

演算子の優先順位が混じるだけでスゲー大変な処理が必要になるな・・・考える。